کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656876 1632988 2014 5 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Triangle-free intersection graphs of line segments with large chromatic number
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Triangle-free intersection graphs of line segments with large chromatic number
چکیده انگلیسی

In the 1970s Erdős asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is no. Specifically, for each positive integer k we construct a triangle-free family of line segments in the plane with chromatic number greater than k. Our construction disproves a conjecture of Scott that graphs excluding induced subdivisions of any fixed graph have chromatic number bounded by a function of their clique number.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series B - Volume 105, March 2014, Pages 6–10
نویسندگان
, , , , , , ,