论文标题
一类具有较大排宽的图形
A class of graphs with large rankwidth
论文作者
论文摘要
我们描述了几个具有较大级别的图形（或与任意大的cliquewidth相同的图形）。 Korpelainen，Lozin和Mayhill [拆分置换图，图形和组合学，30（3）：633-646，2014]证明，存在具有任意较大排水的Dilworth 2的拆分图，但没有明确的构建它们。我们提供明确的结构。 Maffray，Penev和Vušković[Coloring Rings，Graph Demolugion Journal of Graph Doemens 96（4）：642-683，2021]证明，它们称它们称为$ n $ sets上的戒指的图可以在多项式时间内进行彩色。我们表明，对于每个固定的整数$ n \ geq 3 $，都有$ n $ set上的戒指，这些$ sets sets the任意地位。当$ n \ geq 5 $和$ n $很奇怪时，这提供了新的无孔图的新结构，并具有任意较大的排宽。
We describe several graphs with arbitrarily large rankwidth (or equivalently with arbitrarily large cliquewidth). Korpelainen, Lozin, and Mayhill [Split permutation graphs, Graphs and Combinatorics, 30(3):633-646, 2014] proved that there exist split graphs with Dilworth number 2 with arbitrarily large rankwidth, but without explicitly constructing them. We provide an explicit construction. Maffray, Penev, and Vušković [Coloring rings, Journal of Graph Theory 96(4):642-683, 2021] proved that graphs that they call rings on $n$ sets can be colored in polynomial time. We show that for every fixed integer $n\geq 3$, there exist rings on $n$ sets with arbitrarily large rankwidth. When $n\geq 5$ and $n$ is odd, this provides a new construction of even-hole-free graphs with arbitrarily large rankwidth.
