Triangle-free intersection graphs of line segments with large chromatic number. (English) Zbl 1300.05106
Summary: 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 A. D. Scott [J. Graph Theory 24, No. 4, 297–311 (1997; Zbl 0876.05036)] that graphs excluding induced subdivisions of any fixed graph have chromatic number bounded by a function of their clique number.
MSC:
| 05C15 | Coloring of graphs and hypergraphs |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
Citations:
Zbl 0876.05036References:
| [1] | Asplund, Edgar; Grünbaum, Branko, On a colouring problem, Math. Scand., 8, 181-188 (1960) · Zbl 0095.17002 |
| [2] | Brass, Peter; Moser, William; Pach, János, Research Problems in Discrete Geometry (2005), Springer: Springer New York · Zbl 1086.52001 |
| [3] | Burling, James P., On coloring problems of families of prototypes (1965), University of Colorado: University of Colorado Boulder, PhD thesis |
| [5] | Gyárfás, András, Problems from the world surrounding perfect graphs, Zastos. Mat., 19, 413-441 (1987) · Zbl 0718.05041 |
| [6] | Gyárfás, András; Lehel, Jenő, Covering and coloring problems for relatives of intervals, Discrete Math., 55, 2, 167-180 (1985) · Zbl 0569.05020 |
| [7] | Kostochka, Alexandr; Nešetřil, Jaroslav, Chromatic number of geometric intersection graphs, (Klazar, Martin, 1995 Prague Midsummer Combinatorial Workshop, KAM Series 95-309 (1995), Charles University: Charles University Prague), 43-45 |
| [8] | Kostochka, Alexandr; Nešetřil, Jaroslav, Coloring relatives of intervals on the plane I: chromatic number versus girth, European J. Combin., 19, 1, 103-110 (1998) · Zbl 0886.05064 |
| [9] | McGuinness, Sean, Colouring arcwise connected sets in the plane I, Graphs Combin., 16, 4, 429-439 (2000) · Zbl 0984.05034 |
| [10] | McGuinness, Sean, Colouring arcwise connected sets in the plane II, Graphs Combin., 17, 1, 135-148 (2001) · Zbl 0983.05042 |
| [11] | Mycielski, Jan, Sur le coloriage des graphes, Colloq. Math., 3, 161-162 (1955) · Zbl 0064.17805 |
| [12] | Pach, János; Törőcsik, Jenő, Some geometric applications of Dilworth’s theorem, Discrete Comput. Geom., 12, 1, 1-7 (1994) · Zbl 0799.05018 |
| [13] | Pawlik, Arkadiusz; Kozik, Jakub; Krawczyk, Tomasz; Lasoń, Michał; Micek, Piotr; Trotter, William T.; Walczak, Bartosz, Triangle-free geometric intersection graphs with large chromatic number, Discrete Comput. Geom., 50, 3, 714-726 (2013) · Zbl 1275.05038 |
| [14] | Scott, Alex D., Induced trees in graphs of large chromatic number, J. Graph Theory, 24, 4, 297-311 (1997) · Zbl 0876.05036 |
| [16] | Zykov, Alexander A., On some properties of linear complexes, Mat. Sb. (N.S.), 24(66), 2, 163-188 (1949), (in Russian) · Zbl 0033.02602 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
