Opuscula Math. 42, no. 1 (2022), 65-73
https://doi.org/10.7494/OpMath.2022.42.1.65
Opuscula Mathematica
Edge homogeneous colorings
Tomáš Madaras
Alfréd Onderko
Thomas Schweser
Abstract. We explore four kinds of edge colorings defined by the requirement of equal number of colors appearing, in particular ways, around each vertex or each edge. We obtain the characterization of graphs colorable in such a way that the ends of each edge see (not regarding the edge color itself) \(q\) colors (resp. one end sees \(q\) colors and the color sets for both ends are the same), and a sufficient condition for 2-coloring a graph in a way that the ends of each edge see (with the omission of that edge color) altogether \(q\) colors. The relations of these colorings to \(M_q\)-colorings and role colorings are also discussed; we prove an interpolation theorem for the numbers of colors in edge coloring where all edges around each vertex have \(q\) colors.
Keywords: homogeneous coloring, \(M_q\)-coloring, line graph, role coloring.
Mathematics Subject Classification: 05C15.
- K. Budajová, J. Czap, \(m_2\)-edge coloring and maximum matching of graphs, Int. J. Pure Appl. Math. 88 (2013), no. 2, 161-167.
- J. Czap, \(M_i\)-edge colorings of graphs, Appl. Math. Sci. 5 (2011), no. 49, 2437-2442.
- J. Czap, A note on \(M_2\)-edge colorings of graphs, Opuscula Math. 35 (2015), no. 3, 287-291.
- J. Czap, P. Šugerek, \(M_i\)-edge colorings of complete graphs, Appl. Math. Sci. 9 (2015), no. 77, 3835-3842.
- J. Czap, M. Horňák, S. Jendrol', A survey on the cyclic coloring and its relaxations, Discuss. Math. Graph Theory 41 (2021), 5-38.
- J. Czap, P. Šugerek, J. Ivančo, \(M_2\)-edge colorings of cacti and graph joins, Discuss. Math. Graph Theory 36 (2016), 59-69.
- M.G. Everett, S. Borgatti, Role coloring a graph, Math. Social Sci. 21 (1991), no. 2, 183-188.
- R.J. Faudree, A. Gyárfás, R.H. Schelp, Z. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990), 205-211.
- J.-L. Fouquet, J.-L. Jolivet, Strong edge-colorings of graphs and applications to multi-k-gons, Ars Combin. 16 (1983), 141-150.
- P. van 't Hof, D. Paulusma, J.M.M. van Rooij, Computing role assignments of chordal graphs, Theoret. Comput. Sci. 411 (2010), 3601-3613.
- J. Ivančo, \(M_2\)-edge colorings of dense graphs, Opuscula Math. 36 (2016), no. 5, 603-612.
- M. Janicová, T. Madaras, R. Soták, B. Lužar, From NMNR-coloring of hypergraphs to homogenous coloring of graphs, Ars Math. Contemp. 12 (2017), no. 2, 351-360.
- H. Lei, Y. Shi, A survey on star edge-coloring of graphs, arXiv:2009.08017, 2020.
- X.-S. Liu, K. Deng, An upper bound on the star chromatic index of graphs with \(\delta \geq 7\), J. Lanzhou Univ. Nat. Sci. 44 (2008), 98-100.
- C.St.J.A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. Lond. Math. Soc. 36 (1961), 445-450.
- C.St.J.A. Nash-Williams, Decomposition of finite graphs into forests, J. Lond. Math. Soc. 39 (1964), 12.
- C. Purcell, P. Rombach, On the complexity of role colouring planar graphs, trees and cographs, J. Discrete Algorithms 35 (2015), 1-8.
- F.S. Roberts, L. Sheng, How hard is to determine if a graph has a 2-role assignment?, Networks 37 (2001), 67-73.
- L. Sheng, 2-role assignments on triangulated graphs, Theoret. Comput. Sci. 304 (2003), 201-214.
- M. Šurimová, T. Madaras, Homogeneous colourings of graphs, (2021), submitted.
- Tomáš Madaras (corresponding author)
https://orcid.org/0000-0003-4565-043X- P.J. Šafárik University in Košice, Institute of Mathematics, Faculty of Science, Jesenná 5, 04001 Košice, Slovakia
- Alfréd Onderko
- https://orcid.org/0000-0003-4811-3955
- P.J. Šafárik University in Košice, Institute of Mathematics, Faculty of Science, Jesenná 5, 04001 Košice, Slovakia
- Thomas Schweser
- https://orcid.org/0000-0002-4969-7115
- Technische Universitat Ilmenau, Institute of Mathematics, PF 100565, D-98684 Ilmenau, Germany
- Communicated by Adam Paweł Wojda.
- Received: 2021-07-28.
- Revised: 2021-09-24.
- Accepted: 2021-09-30.
- Published online: 2022-01-20.
