A class of graphs with large rankwidth.

2020 
We describe several graphs of arbitrarily large rankwidth (or equivalently of arbitrarily large cliquewidth). Korpelainen, Lozin, and Mayhill [Split permutation graphs, {\em Graphs and Combinatorics}, 30(3):633--646, 2014] proved that there exist split graphs with Dilworth number~2 of arbitrarily large rankwidth, but without explicitly constructing them. Our construction provides an explicit construction. Maffray, Penev, and Vu\v{s}kovi\'c [Coloring rings, arXiv:1907.11905, 2019] proved that graphs that they call rings on $n$ sets can be colored in polynomial time. Our construction shows that for some fixed integer $n\geq 3$, there exist rings on $n$ sets of arbitrarily large rankwidth. When $n\geq 5$ and $n$ is odd, this provides a new construction of even-hole-free graphs of arbitrarily large rankwidth.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    14
    References
    0
    Citations
    NaN
    KQI
    []