Abstract
A decomposition of a non-empty simple graph G is a pair [G,P] such that P is a set of non-empty induced subgraphs of G, and every edge of G belongs to exactly one subgraph in P. The chromatic index \(\chi'([G,P])\) of a decomposition [G,P] is the smallest number k for which there exists a k-coloring of the elements of P in such a way that for every element of P all of its edges have the same color, and if two members of P share at least one vertex, then they have different colors. A long standing conjecture of Erdős–Faber–Lovász states that every decomposition \([K_{n}, P]\) of the complete graph \(K_n\) satisfies \(\chi'([K_{n}, P])\leq n\). In this paper we work with geometric graphs, and inspired by this formulation of the conjecture, we introduce the concept of chromatic index of a decomposition of the complete geometric graph. We present bounds for the chromatic index of several types of decompositions when the vertices of the graph are in general position. We also consider the particular case when the vertices are in convex position and present bounds for the chromatic index of a few types of decompositions.
Similar content being viewed by others
References
Aichholzer, O., Araujo-Pardo, G., García-Colín, N., Hackl, T., Lara, D., Rubio-Montiel, C., Urrutia, J.: Geometric achromatic and pseudoachromatic indices. Graphs Combin. 32, 431–451 (2016)
Araujo, G., Dumitrescu, A., Hurtado, F., Noy, M., Urrutia, J.: On the chromatic number of some geometric type Kneser graphs. Comput. Geom. 32, 59–69 (2005)
G. Araujo-Pardo, C. Rubio-Montiel, and A. Vázquez-Ávila, Note on the Erdős-Faber-Lovász Conjecture: quasigroups and complete digraphs, Ars Combin. (in press)
Araujo-Pardo, G., Vázquez-Ávila, A.: A note on Erdős-Faber-Lovász conjecture and edge coloring of complete graphs. Ars Combin. 129, 287–298 (2016)
R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes. II, Proc. London Math. Soc. (3), 83 (2001), 532–562
B. Bukh, A point in many triangles, Electron. J. Combin., 13 (2006), Note 10, 3 pp
J. Cano, L. F. Barba, T. Sakai, and J. Urrutia, On edge-disjoint empty triangles of point sets, in: Thirty Essays on Geometric Graph Theory, Springer (New York, 2013), pp. 83–100
Ceder, J.G.: Generalized sixpartite problems. Bol. Soc. Mat. Mexicana 9, 28–32 (1964)
Colbourn, C.J., Colbourn, M.J.: The chromatic index of cyclic Steiner \(2\)-designs. Internat. J. Math. Math. Sci. 5, 823–825 (1982)
C. J. Colbourn, A. D. Forbes, M. J. Grannell, T. S. Griggs, P. Kaski, P. R. J. Östergård, D. A. Pike, and O. Pottonen, Properties of the Steiner triple systems of order 19, Electron. J. Combin., 17 (2010), Research Paper 98, 30 pp
Colbourn, C.J., Rosa, A.: Triple Systems. The Clarendon Press, Oxford University Press (New York, Oxford Mathematical Monographs (1999)
Erdős, P.: On sets of distances of \(n\) points. Amer. Math. Monthly 53, 248–250 (1946)
P. Erdős, Problems and results in graph theory and combinatorial analysis, in: Proc. Fifth Brit. Comb. Conf. (Univ. Aberdeen, Aberdeen, 1975) (Winnipeg, Man.), Utilitas Math. (1976), pp. 169–192
Fabila-Monroy, R., Wood, D.R.: Colouring the triangles determined by a point set. J. Comput. Geom. 3, 86–101 (2012)
Hirschfeld, J.W.P.: Projective Geometries over Finite Fields, 2nd edn. The Clarendon Press, Oxford University Press (New York, Oxford Mathematical Monographs (1998)
Kiss, G., Rubio-Montiel, C.: A note on \(m\)-factorizations of complete multigraphs arising from designs. Ars Math. Contemp. 8, 163–175 (2015)
Peltesohn, R.: Eine Lösung der beiden Heffterschen Differenzenprobleme. Compositio Math. 6, 251–257 (1939)
D. K. Ray-Chaudhuri and R. M. Wilson, Solution of Kirkman's schoolgirl problem, in: Combinatorics (Proc. Sympos. Pure Math., Vol. XIX, Univ. California, Los Angeles, Calif., 1968), Amer. Math. Soc. (Providence, RI, 1971), pp. 187–203
Roldán-Pensado, E., Soberón, P.: An extension of a theorem of Yao and Yao. Discrete Comput. Geom. 51, 285–299 (2014)
D. Romero and F. Alonso-Pecina, The Erdős–Faber–Lovász conjecture is true for \({n\le 12}\), Discrete Math. Algorithms Appl., 6 (2014), 1450039, 5 pp
Romero, D., Sánchez-Arroyo, A.: Adding evidence to the Erdős-Faber-Lovász Conjecture. Ars Combin. 85, 71–84 (2007)
Acknowledgement
We thank the anonymous referee for helpful suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 734922.
C. Huemer was supported by projects MINECO MTM2015-63791-R and Gen. Cat. DGR 2017SGR1336.
C.Rubio-Montiel was partially supported by a CONACyT-México Postdoctoral fellowship, by the National scholarship programme of the Slovak Republic and PAIDI/007/19.
Rights and permissions
About this article
Cite this article
Huemer, C., Lara, D. & Rubio-Montiel, C. Coloring decompositions of complete geometric graphs. Acta Math. Hungar. 159, 429–446 (2019). https://doi.org/10.1007/s10474-019-00963-0
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10474-019-00963-0