کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
8902829 1632393 2018 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Chromatic bounds for some classes of 2K2-free graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Chromatic bounds for some classes of 2K2-free graphs
چکیده انگلیسی
A hereditary class G of graphs is χ-bounded if there is a χ-binding function, say f such that χ(G)≤f(ω(G)), for every G∈G, where χ(G) (ω(G)) denotes the chromatic (clique) number of G. It is known that for every 2K2-free graph G, χ(G)≤ω(G)+12, and the class of (2K2,3K1)-free graphs does not admit a linear χ-binding function. In this paper, we are interested in classes of 2K2-free graphs that admit a linear χ-binding function. We show that the class of (2K2,H)-free graphs, where H∈{K1+P4,K1+C4,P2∪P3¯,HVN,K5−e,K5} admits a linear χ-binding function. Also, we show that some superclasses of 2K2-free graphs are χ-bounded.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 341, Issue 11, November 2018, Pages 3079-3088
نویسندگان
, ,