×

Coloring Jordan regions and curves. (English) Zbl 1368.05058

Summary: A Jordan region is a subset of the plane that is homeomorphic to a closed disk. Consider a family \(\mathcal{F}\) of Jordan regions whose interiors are pairwise disjoint, and such that any two Jordan regions intersect in at most one point. If any point of the plane is contained in at most \(k\) elements of \(\mathcal{F}\) (with \(k\) sufficiently large), then we show that the elements of \(\mathcal{F}\) can be colored with at most \(k+1\) colors so that intersecting Jordan regions are assigned distinct colors. This is best possible and answers a question raised by B. A. Reed and F. B. Shepherd [Combinatorica 16, No. 4, 555–566 (1996; Zbl 0880.05071)]. As a simple corollary, we also obtain a positive answer to a problem of P. Hliněný [Discrete Appl. Math. 81, No. 1–3, 59–68 (1998; Zbl 0898.05025)] on the chromatic number of contact systems of strings. We also investigate the chromatic number of families of touching Jordan curves. This can be used to bound the ratio between the maximum number of vertex-disjoint directed cycles in a planar digraph, and its fractional counterpart.

MSC:

05C15 Coloring of graphs and hypergraphs
05C10 Planar graphs; geometric and topological aspects of graph theory
05C20 Directed graphs (digraphs), tournaments

References:

[1] O. Amini, L. Esperet, and J. van den Heuvel, {\it A unified approach to distance-two colouring of graphs on surfaces}, Combinatorica, 33 (2013), pp. 253-296, . · Zbl 1324.05052
[2] L. Esperet, D. Gonçalves, and A. Labourel, {\it Coloring non-crossing strings}, Electron. J. Combin., 23 (2016), #P4.4. · Zbl 1351.05073
[3] P. Erdös, A. L. Rubin, and H. Taylor, {\it Choosability in graphs}, Congr. Numer., 26 (1979), pp. 125-157.
[4] J. Fox and J. Pach, {\it Touching Strings}, manuscript, 2012.
[5] M. X. Goemans and D. P. Williamson, {\it Primal-dual approximation algorithms for feedback problems in planar graphs}, Combinatorica, 17 (1997), pp. 1-23, .
[6] P. Hliněný, {\it The maximal clique and colourability of curve contact graphs}, Discrete Appl. Math., 81 (1998), pp. 59-68, . · Zbl 0898.05025
[7] R. J. Kang and T. Müller, {\it Arrangements of pseudocircles and circles}, Discrete Comput. Geom., 51 (2014), pp. 896-925, . · Zbl 1298.52028
[8] A. Kostochka, {\it Coloring intersection graphs of geometric figures with a given clique number}, in Towards a Theory of Geometric Graphs, J. Pach, ed., Contemp. Math. 342, AMS, Providence, RI, 2004, pp. 127-138. · Zbl 1064.05059
[9] P. Ossona de Mendez, {\it The reduced genus of a multigraph}, in Proceedings of the 16th Annual Symposium on Theoretical Aspects of Computer Science (STACS 99), Trier, Germany, 1999, pp. 16-31. · Zbl 0928.05043
[10] B. A. Reed and F. B. Shepherd, {\it The Gallai-Younger conjecture for planar graphs}, Combinatorica, 16 (1996), pp. 555-566, . · Zbl 0880.05071
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.