Advertisement
Published in:
2017 | OriginalPaper | Chapter
On Low Rank-Width Colorings
Authors : O-joung Kwon, Michał Pilipczuk, Sebastian Siebertz
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
We introduce the concept of low rank-width colorings, generalizing the notion of low tree-depth colorings introduced by Nešetřil and Ossona de Mendez in [26]. We say that a class \(\mathcal {C}\) of graphs admits low rank-width colorings if there exist functions \(N:\mathbb {N}\rightarrow \mathbb {N}\) and \(Q:\mathbb {N}\rightarrow \mathbb {N}\) such that for all \(p\in \mathbb {N}\), every graph \(G\in \mathcal {C}\) can be vertex colored with at most N(p) colors such that the union of any \(i\le p\) color classes induces a subgraph of rank-width at most Q(i).
Graph classes admitting low rank-width colorings strictly generalize graph classes admitting low tree-depth colorings and graph classes of bounded rank-width. We prove that for every graph class \(\mathcal {C}\) of bounded expansion and every positive integer r, the class \(\{G^r:G\in \mathcal {C}\}\) of rth powers of graphs from \(\mathcal {C}\), as well as the classes of unit interval graphs and bipartite permutation graphs admit low rank-width colorings. All of these classes have unbounded rank-width and do not admit low tree-depth colorings. We also show that the classes of interval graphs and permutation graphs do not admit low rank-width colorings. As interesting side properties, we prove that every graph class admitting low rank-width colorings has the Erdős-Hajnal property and is \(\chi \)-bounded.