On low rank-width colorings. (January 2020) - Kwon, O-joung; Pilipczuk, Michał; Siebertz, Sebastian
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 (2008). We say that a class C of graphs admits low rank-width colorings if there exist functions N : N → N and Q : N → N such that for all p ∈ N, every graph G ∈ C can be vertex colored with at most N ( p ) colors such that the union of any i ≤ 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 C of bounded expansion and every positive integer  r, the class { G r : G ∈ C } of r th powers of graphs from  C admits low rank-width colorings. On the negative side, we 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 hereditary graph class admitting low rank-width colorings has the Erdős–Hajnal property and is χ -bounded.