Chromatic number of intersection graphs of segments with two slopes

EUROCOMB’23

Abstract
A $d$-dir graph is an intersection graph of segments, where the segments have at most $d$ different slopes. It is easy to see that a $d$-dir graph with clique number $\omega$ has chromatic number at most $d\omega$. We study the chromatic number of $2$-dir graphs in more detail, proving that this upper bound is tight even in the fractional coloring setting.

Pages:
127–133
References

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.

Metrics

0

Views

0

PDF views