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

چکیده انگلیسی
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
Journal: European Journal of Combinatorics - Volume 33, Issue 4, May 2012, Pages 679–683
نویسندگان
Zdeněk Dvořák, Daniel Král’,