On low rank-width colorings

O-joung Kwon (권오정)

Technische Universitat Berlin, Berin, Germany

Technische Universitat Berlin, Berin, Germany

2017/6/09

**Friday 11AM** 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

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.