Chromatic number of intersection graphs of segments with two slopes
EUROCOMB’23
127–133
E. Asplund and B. Grünbaum. On a colouring problem. Math. Scand., 8:181-188, 1960.
https://doi.org/10.7146/math.scand.a-10607
James Perkins Burling. On coloring problems of families of prototypes (phd thesis). University of Colorado, Boulder, 1965.
Marco Caoduro, Jana Cslovjecsek, Michał Pilipczuk, and Karol Węgrzycki. Independence number of intersection graphs of axis-parallel segments. arXiv, 2205.15189, 2022.
Jérémie Chalopin and Daniel Gonçalves. Every planar graph is the intersection graph of segments in the plane. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 631-638, 2009.
https://doi.org/10.1145/1536414.1536500
M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. Annals of Mathematics, 164:51-229, 2006.
https://doi.org/10.4007/annals.2006.164.51
James Davies and Rose McCarty. Circle graphs are quadratically χ-bounded. Bulletin of the London Mathematical Society, 53(3), 2021.
https://doi.org/10.1112/blms.12447
Hubert de Fraysseix, Patrice Ossona de Mendez, and Janos Pach. Representation of planar graphs by segments. Intuitive Geometry, 63:109-117, 1991.
P. Erdős. Graph theory and probability. Canad. J. Math, 11:34-38, 1959.
https://doi.org/10.4153/CJM-1959-003-9
Daniel Gonçalves. 3-colorable planar graphs have an intersection segment representation using 3 slopes. In Graph-Theoretic Concepts in Computer Science: 45th International Workshop, WG 2019, Vall de Núria, Spain, June 19-21, 2019, Revised Papers 45, pages 351-363. Springer, 2019.
https://doi.org/10.1007/978-3-030-30786-8_27
András Gyárfás. On the chromatic number of multiple interval graphs and overlap graphs. Discrete mathematics, 55(2):161-166, 1985.
https://doi.org/10.1016/0012-365X(85)90044-5
András Gyárfás. Problems from the world surrounding perfect graphs. Applicationes Mathematicae, 19(3-4):413-441, 1987.
https://doi.org/10.4064/am-19-3-4-413-441
I Ben-Arroyo Hartman, Ilan Newman, and Ran Ziv. On grid intersection graphs. Discrete Mathematics, 87(1):41-52, 1991.
https://doi.org/10.1016/0012-365X(91)90069-E
Seog-Jin Kim, Alexandr Kostochka, and Kittikorn Nakprasit. On the chromatic number of intersection graphs of convex sets in the plane. the electronic journal of combinatorics, 11(1):R52, 2004.
https://doi.org/10.37236/1805
Jan Kratochvíl and Jiří Matoušek. Intersection graphs of segments. Journal of Combinatorial Theory, Series B, 62(2):289-315, 1994.
https://doi.org/10.1006/jctb.1994.1071
László Lovász. Kneser's conjecture, chromatic number, and homotopy. Journal of Combinatorial Theory, Series A, 25:319-324, 1978.
https://doi.org/10.1016/0097-3165(78)90022-5
Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T Trotter, and Bartosz Walczak. Triangle-free intersection graphs of line segments with large chromatic number. Journal of Combinatorial Theory, Series B, 105:6-10, 2014.
https://doi.org/10.1016/j.jctb.2013.11.001
Edward R. Scheinerman and Daniel H. Ullman. Fractional graph theory. Dover Publications Inc., Mineola, NY, 2011.
Andrew Suk. Coloring intersection graphs of x-monotone curves in the plane. Combinatorica, 34(4):487-505, 2014.
https://doi.org/10.1007/s00493-014-2942-5
D. West. Open problems. SIAM J. Discrete Math. Newslett., 2:10-12, 1991.

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Sudatta Bhattacharya, Zdenek Dvorak, Fariba Noorizadeh