کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4653772 1632797 2012 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Classes of graphs with small rank decompositions are χχ-bounded
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Classes of graphs with small rank decompositions are χχ-bounded
چکیده انگلیسی

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


► Tree decomposition of small rank over a χχ-bounded class implies χχ-boundedness.
► Graphs of bounded rank-width are χχ-bounded.
► 1-joins preserve χχ-boundedness.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Combinatorics - Volume 33, Issue 4, May 2012, Pages 679–683
نویسندگان
, ,