| کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن | 
|---|---|---|---|---|
| 5777102 | 1632570 | 2017 | 6 صفحه PDF | دانلود رایگان | 
عنوان انگلیسی مقاله ISI
												Burling graphs, chromatic number, and orthogonal tree-decompositions
												
											دانلود مقاله + سفارش ترجمه
													دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
																																												موضوعات مرتبط
												
													مهندسی و علوم پایه
													ریاضیات
													ریاضیات گسسته و ترکیبات
												
											پیش نمایش صفحه اول مقاله
												 
												چکیده انگلیسی
												A classic result of Asplund and Grünbaum states that intersection graphs of axis-aligned rectangles in the plane are Ï-bounded. This theorem can be equivalently stated in terms of path-decompositions as follows: There exists a function f:NâN such that every graph that has two path-decompositions such that each bag of the first decomposition intersects each bag of the second in at most k vertices has chromatic number at most f(k). Recently, DujmoviÄ, Joret, Morin, Norin, and Wood asked whether this remains true more generally for two tree-decompositions. In this note we provide a negative answer: There are graphs with arbitrarily large chromatic number for which one can find two tree-decompositions such that each bag of the first decomposition intersects each bag of the second in at most two vertices. Furthermore, this remains true even if one of the two decompositions is restricted to be a path-decomposition. This is shown using a construction of triangle-free graphs with unbounded chromatic number due to Burling, which we believe should be more widely known.
											ناشر
												Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 415-420
											Journal: Electronic Notes in Discrete Mathematics - Volume 61, August 2017, Pages 415-420
نویسندگان
												Stefan Felsner, Gwenaël Joret, Piotr Micek, William T. Trotter, Veit Wiechert,