











Title 


Speaker 
권오정 


Date 
20170609 


Host 



Place 
KAIST 




Abstract : We introduce the concept of low rankwidth colorings, generalizing the notion of low treedepth 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 C of graphs admits low rankwidth colorings if there exist functions N:ℕ→ℕ and Q:ℕ→ℕ such that for all p∈ℕ, 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 rankwidth at most Q(i).
Graph classes admitting low rankwidth colorings strictly generalize graph classes admitting low treedepth colorings and graph classes of bounded rankwidth. We prove that for every graph class C of bounded expansion and every positive integer r, the class {Gr: G∈C} of rth powers of graphs from C, as well as the classes of unit interval graphs and bipartite permutation graphs admit low rankwidth colorings. All of these classes have unbounded rankwidth and do not admit low treedepth colorings. We also show that the classes of interval graphs and permutation graphs do not admit low rankwidth 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. 





