Opuscula Mathematica
Opuscula Math. 36, no. 5 (2016), 603-612

M<sub>2</sub>-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)
References ▼
  1. [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. [2] J. Czap, \(\mathrm{M}_{i}\)-edge colorings of graphs, Appl. Math. Sci. 5 (2011), 2437-2442.
  3. [3] J. Czap, A note on \(\mathrm{M}_{2}\)-edge colorings of graphs, Opuscula Math. 35 (2015), 287-291.
  4. [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.
About the authors ▼
Jaroslav Ivančo
Institute of Mathematics, P. J. Šafárik University, Jesenná 5, 041 54 Košice, Slovakia
About the article ▼
Communicated by Mariusz Meszka.
Received: 2015-06-19.
Revised: 2016-02-24.
Accepted: 2016-02-24.
Published online: 2016-06-29.
Cite this article as ▼
Jaroslav Ivančo, M<sub>2</sub>-edge colorings of dense graphs, Opuscula Math. 36, no. 5 (2016), 603-612, http://dx.doi.org/10.7494/OpMath.2016.36.5.603.
Download this article's citation as: