Edge homogeneous colorings

• Autorzy: Madaras Tomáš , Onderko Alfréd , Schweser Thomas

Identyfikatory

DOI

10.7494/OpMath.2022.42.1.65

• Języki publikacji: EN

Abstrakty

EN

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 Mq-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.

Słowa kluczowe

EN

homogeneous coloring; Mq-coloring; line graph; role coloring

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2022
• Tom: Vol. 42, no. 1
• Strony: 65--73
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Madaras Tomáš

• P.J. Šafárik University in Košice, Institute of Mathematics, Faculty of Science, Jesenná 5, 04001 Košice, Slovakia

• https://orcid.org/0000-0003-4565-043X

autor

Onderko Alfréd

• P.J. Šafárik University in Košice, Institute of Mathematics, Faculty of Science, Jesenná 5, 04001 Košice, Slovakia

• https://orcid.org/0000-0003-4811-3955

autor

Schweser Thomas

• Technische Universitat Ilmenau, Institute of Mathematics, PF 100565, D-98684 Ilmenau, Germany

• https://orcid.org/0000-0002-4969-7115

Bibliografia

• [1] K. Budajová, J. Czap, m2-edge coloring and maximum matching of graphs, Int. J. Pure Appl. Math. 88 (2013), no. 2, 161–167.
• [2] J. Czap, Mi-edge colorings of graphs, Appl. Math. Sci. 5 (2011), no. 49, 2437–2442.
• [3] J. Czap, A note on M2-edge colorings of graphs, Opuscula Math. 35 (2015), no. 3, 287–291.
• [4] J. Czap, P. Šugerek, Mi-edge colorings of complete graphs, Appl. Math. Sci. 9 (2015), no. 77, 3835–3842.
• [5] J. Czap, M. Horňák, S. Jendrol’, A survey on the cyclic coloring and its relaxations, Discuss. Math. Graph Theory 41 (2021), 5–38.
• [6] J. Czap, P. Šugerek, J. Ivančo, M2-edge colorings of cacti and graph joins, Discuss. Math. Graph Theory 36 (2016), 59–69.
• [7] M.G. Everett, S. Borgatti, Role coloring a graph, Math. Social Sci. 21 (1991), no. 2, 183–188.
• [8] R.J. Faudree, A. Gyárfás, R.H. Schelp, Z. Tuza, The strong chromatic index of graphs, Ars Combin. 29B (1990), 205–211.
• [9] J.-L. Fouquet, J.-L. Jolivet, Strong edge-colorings of graphs and applications to multi-k-gons, Ars Combin. 16 (1983), 141–150.
• [10] P. van ’t Hof, D. Paulusma, J.M.M. van Rooij, Computing role assignments of chordal graphs, Theoret. Comput. Sci. 411 (2010), 3601–3613.
• [11] J. Ivančo, M2-edge colorings of dense graphs, Opuscula Math. 36 (2016), no. 5, 603–612.
• [12] 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.
• [13] H. Lei, Y. Shi, A survey on star edge-coloring of graphs, arXiv:2009.08017, 2020.
• [14] X.-S. Liu, K. Deng, An upper bound on the star chromatic index of graphs with δ ≥ 7, J. Lanzhou Univ. Nat. Sci. 44 (2008), 98–100.
• [15] C.St.J.A. Nash-Williams, Edge-disjoint spanning trees of finite graphs, J. Lond. Math. Soc. 36 (1961), 445–450.
• [16] C.St.J.A. Nash-Williams, Decomposition of finite graphs into forests, J. Lond. Math. Soc. 39 (1964), 12.
• [17] C. Purcell, P. Rombach, On the complexity of role colouring planar graphs, trees and cographs, J. Discrete Algorithms 35 (2015), 1–8.
• [18] F.S. Roberts, L. Sheng, How hard is to determine if a graph has a 2-role assignment?, Networks 37 (2001), 67–73.
• [19] L. Sheng, 2-role assignments on triangulated graphs, Theoret. Comput. Sci. 304 (2003), 201–214.
• [20] M. Šurimová, T. Madaras, Homogeneous colourings of graphs, (2021), submitted.

Uwagi

Opracowanie rekordu ze środków MEiN, umowa nr SONP/SP/546092/2022 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2022-2023).