A class of graphs with large rankwidth

DOI10.1016/J.DISC.2023.113699zbMATH Open1525.05161arXiv2007.11513OpenAlexW4287708960MaRDI QIDQ6080165FDOQ6080165

Authors: Chính T. Hoàng, Nicolas Trotignon 

Publication date: 30 October 2023

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: 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 Vuv{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 $ngeq3$, there exist rings on $n$ sets of arbitrarily large rankwidth. When $ngeq5$ and $n$ is odd, this provides a new construction of even-hole-free graphs of arbitrarily large rankwidth.

Full work available at URL: https://arxiv.org/abs/2007.11513

Recommendations

• On rank-width of (diamond, even-hole)-free graphs
• Bipartite graphs of large clique-width
• On low rank-width colorings
• On low rank-width colorings
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels

zbMATH Keywords

ringseven-hole-free graphscliquewidthDilworth numberrankwidth

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Cites Work

• Linear time solvable optimization problems on graphs of bounded clique-width
• Handle-rewriting hypergraph grammars
• Approximating clique-width and branch-width
• On the clique-width of some perfect graph classes
• Clique-width for hereditary graph classes
• Split permutation graphs
• Well-quasi-order of relabel functions
• On rank-width of (diamond, even-hole)-free graphs
• Structure and algorithms for (cap, even hole)-free graphs
• Colouring diamond-free graphs
• On low rank-width colorings
• A bound on the treewidth of planar even-hole-free graphs
• Bounding the clique-width of \(H\)-free split graphs
• On the structure of (pan, even hole)-free graphs
• Well-quasi-ordering versus clique-width
• Bounding the Clique‐Width of H‐Free Chordal Graphs
• Graph isomorphism for \((H_1, H_2)\)-free graphs: an almost complete dichotomy
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• Coloring rings

This page was built for publication: A class of graphs with large rankwidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6080165)