Triangle-free intersection graphs of line segments with large chromatic number

Bibliographic description

punktacja MEiN [2014 A]: 35

title:	Triangle-free intersection graphs of line segments with large chromatic number
author:	Pawlik Arkadiusz , Kozik Jakub , Krawczyk Tomasz , Lasoń Michał , Micek Piotr , Trotter William T., Walczak Bartosz
journal title:	Journal of Combinatorial Theory. Series B
volume:	105
date of publication :	2014
pages:	6-10
ISSN:	0095-8956
eISSN:	1096-0902
DOI:	10.1016/j.jctb.2013.11.001
URL:	http://www.sciencedirect.com/science/article/pii/S009589561300083X
language:	English
journal language:	English
abstract in English:	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.
keywords in other languages:	Intersection graph, Line segments, Triangle-free, Chromatic number
affiliation:	Wydział Matematyki i Informatyki : Zespół Katedr i Zakładów Informatyki Matematycznej
type:	journal article
subtype:	academic paper

Files	Size	Format	View
There are no files associated with this item.