×

zbMATH — the first resource for mathematics

The chromatic number of the convex segment disjointness graph. (English) Zbl 1375.68131
Márquez, Alberto (ed.) et al., Computational geometry. XIV Spanish meeting on computational geometry, EGC 2011, dedicated to Ferran Hurtado on the occasion of his 60th birthday, Alcalá de Henares, Spain, June 27–30, 2011. Revised selected papers. Berlin: Springer (ISBN 978-3-642-34190-8/pbk). Lecture Notes in Computer Science 7579, 79-84 (2012).
Summary: Let \(P\) be a set of \(n\) points in general and convex position in the plane. Let \(D_{n}\) be the graph whose vertex set is the set of all line segments with endpoints in \(P\), where disjoint segments are adjacent. The chromatic number of this graph was first studied by G. Araujo et al. [Comput. Geom. 32, No. 1, 59–69 (2005; Zbl 1067.05023)]. The previous best bounds are \(\frac{3n}{4}\leq \chi(D_n) <n-\sqrt{\frac{n}{2}}\) (ignoring lower order terms). In this paper we improve the lower bound to \(\chi(D_n)\geq n-\sqrt{2n}\), achieving near-tight bounds on \(\chi (D_{n})\).
For the entire collection see [Zbl 1253.68016].

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
05C15 Coloring of graphs and hypergraphs
68R10 Graph theory (including graph drawing) in computer science
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Araujo, G., Dumitrescu, A., Hurtado, F., Noy, M., Urrutia, J.: On the chromatic number of some geometric type Kneser graphs. Comput. Geom. Theory Appl. 32(1), 59–69 (2005) · Zbl 1067.05023 · doi:10.1016/j.comgeo.2004.10.003
[2] Cairns, G., Nikolayevsky, Y.: Bounds for generalized thrackles. Discrete Comput. Geom. 23(2), 191–206 (2000) · Zbl 0959.05030 · doi:10.1007/PL00009495
[3] Cairns, G., Nikolayevsky, Y.: Generalized thrackle drawings of non-bipartite graphs. Discrete Comput. Geom. 41(1), 119–134 (2009) · Zbl 1191.05032 · doi:10.1007/s00454-008-9095-5
[4] Cairns, G., Nikolayevsky, Y.: Outerplanar thrackles. Graphs and Combinatorics 28(1), 85–96 (2012) · Zbl 1234.05168 · doi:10.1007/s00373-010-1010-1
[5] Dujmović, V., Wood, D.R.: Thickness and antithickness (2010) (in preparation)
[6] Fenchel, W., Sutherland, J.: Lösung der aufgabe 167. Jahresbericht der Deutschen Mathematiker-Vereinigung 45, 33–35 (1935)
[7] Hopf, H., Pammwitz, E.: Aufgabe no. 167. Jahresbericht der Deutschen Mathematiker-Vereinigung 43 (1934)
[8] Lovász, L., Pach, J., Szegedy, M.: On Conway’s thrackle conjecture. Discrete Comput. Geom. 18(4), 369–376 (1997) · Zbl 0892.05017 · doi:10.1007/PL00009322
[9] Woodall, D.R.: Thrackles and deadlock. In: Combinatorial Mathematics and its Applications (Proc. Conf., Oxford, 1969), pp. 335–347. Academic Press, London (1971)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.