KAIST Discrete Math Seminar

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 [Grad and classes with bounded expansion I. Decompositions. EJC 2008]. We say that a class ? of graphs admits low rank-width colorings if there exist functions N:ℕ→ℕ and Q:ℕ→ℕ such that for all p∈ℕ, every graph G∈? 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 ? of bounded expansion and every positive integer r, the class {G^r: G∈?} of r-th powers of graphs from ?, 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. In this talk, we provide the color refinement technique necessary to show the first result. This is joint work with Sebastian Sierbertz and Michał Pilipczuk.