pith. machine review for the scientific record. sign in

arxiv: 1107.2161 · v1 · submitted 2011-07-11 · 🧮 math.CO

Recognition: unknown

Classes of graphs with small rank decompositions are chi-bounded

Authors on Pith no claims yet
classification 🧮 math.CO
keywords graphschi-boundedclassboundedeverynumberranksmall
0
0 comments X
read the original abstract

A class of graphs G is chi-bounded if the chromatic number of graphs in G is bounded by a function of the clique number. We show that if a class G is chi-bounded,then every class of graphs admitting a decomposition along cuts of small rank to graphs from G is chi-bounded. As a corollary, we obtain that every class of graphs with bounded rank-width (or equivalently, clique-width) is chi-bounded.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.