A class of graphs with large rankwidth

07/22/2020

∙

by   Chính Hoàng, et al.

∙

0

∙

share

We describe several graphs of arbitrarily large rankwidth (or equivalently of 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 of arbitrarily large rankwidth, but without explicitly constructing them. Our construction provides an explicit construction. Maffray, Penev, and Vušković [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≥ 3, there exist rings on n sets of arbitrarily large rankwidth. When n≥ 5 and n is odd, this provides a new construction of even-hole-free graphs of arbitrarily large rankwidth.