On low rank-width colorings. (January 2020)

• Record Type: Journal Article
• Authors: Kwon, O-joung; Pilipczuk, Michał; Siebertz, Sebastian
• Is Part Of: European journal of combinatorics. Volume 83(2020)
• Publication Date: 2020-01
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2019.103002
• Languages: English
• ISSNs: 0195-6698

Abstract

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.