Opuscula Math. 36, no. 5 (2016), 603-612
http://dx.doi.org/10.7494/OpMath.2016.36.5.603

Opuscula Mathematica

# M2-edge colorings of dense graphs

Jaroslav Ivančo

Abstract. An edge coloring $$\varphi$$ of a graph $$G$$ is called an $$\mathrm{M}_i$$-edge coloring if $$|\varphi(v)|\leq i$$ for every vertex $$v$$ of $$G$$, where $$\varphi(v)$$ is the set of colors of edges incident with $$v$$. Let $$\mathcal{K}_i(G)$$ denote the maximum number of colors used in an $$\mathrm{M}_i$$-edge coloring of $$G$$. In this paper we establish some bounds of $$\mathcal{K}_2(G)$$, present some graphs achieving the bounds and determine exact values of $$\mathcal{K}_2(G)$$ for dense graphs.

Keywords: edge coloring, dominating set, dense graphs.

Mathematics Subject Classification: 05C15.

Full text (pdf)

1. K. Budajová, J. Czap, $$\mathrm{M}_{2}$$-edge coloring and maximum matching of graphs, Int. J. Pure Appl. Math. 88 (2013), 161-167.
2. J. Czap, $$\mathrm{M}_{i}$$-edge colorings of graphs, Appl. Math. Sci. 5 (2011), 2437-2442.
3. J. Czap, A note on $$\mathrm{M}_{2}$$-edge colorings of graphs, Opuscula Math. 35 (2015), 287-291.
4. J. Czap, J. Ivančo, P. Šugerek, $$\mathrm{M}_{2}$$-edge colorings of cacti and graph joins, Discuss. Math. Graph Theory 36 (2016), 59-69.
• Jaroslav Ivančo
• Institute of Mathematics, P. J. Šafárik University, Jesenná 5, 041 54 Košice, Slovakia
• Communicated by Mariusz Meszka.
• Revised: 2016-02-24.
• Accepted: 2016-02-24.
• Published online: 2016-06-29.