1. bookVolume 42 (2022): Issue 4 (November 2022)
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

On Mf-Edge Colorings of Graphs

Published Online: 12 Jul 2022
Volume & Issue: Volume 42 (2022) - Issue 4 (November 2022)
Page range: 1075 - 1088
Received: 03 Dec 2019
Accepted: 30 Apr 2020
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

An edge coloring φ of a graph G is called an Mf-edge coloring if | φ(v)| ≤ f(v) for every vertex v of G, where φ(v) is the set of colors of edges incident with v and f is a function which assigns a positive integer f(v) to each vertex v. Let 𝒦f (G) denote the maximum number of colors used in an Mf-edge coloring of G. In this paper we establish some bounds on 𝒦f(G), present some graphs achieving the bounds and determine exact values of 𝒦f(G) for some special classes of graphs.

Keywords

MSC 2010

[1] A. Adamaszek and A. Popa, Approximation and hardness results for the maximum edge q-coloring problem, J. Discrete Algorithms 38–41 (2016) 1–8. https://doi.org/10.1016/j.jda.2016.09.003 Search in Google Scholar

[2] S. Akbari, N. Alipourfard, P. Jandaghi and M. Mirtaheri, On N2-vertex coloring of graphs, Discrete Math. Algorithms Appl. 10 (2018) 1850007. https://doi.org/10.1142/S1793830918500076 Search in Google Scholar

[3] K. Budajová and J. Czap, M2-edge coloring and maximum matching of graphs, Int. J. Pure Appl. Math. 88 (2013) 161–167. https://doi.org/10.12732/ijpam.v88i2.1 Search in Google Scholar

[4] J. Czap, Mi-edge colorings of graphs, Appl. Math. Sci. 5 (2011) 2437–2442. Search in Google Scholar

[5] J. Czap, A note on M2-edge colorings of graphs, Opuscula Math. 35 (2015) 287–291. https://doi.org/10.7494/OpMath.2015.35.3.287 Search in Google Scholar

[6] J. Czap and P.Šugerek, Mi-edge colorings of complete graphs, Appl. Math. Sci. 9 (2015) 3835–3842. https://doi.org/10.12988/ams.2015.53264 Search in Google Scholar

[7] J. Czap, P.Šugerek and J. Ivančo, M2-edge colorings of cacti and graph joins, Discuss. Math. Graph Theory 36 (2016) 59–69. https://doi.org/10.7151/dmgt.1842 Search in Google Scholar

[8] W. Feng, L. Zang and H. Wang, Approximation algorithm for maximum edge coloring, Theoret. Comput. Sci. 410 (2009) 1022–1029. https://doi.org/10.1016/j.tcs.2008.10.035 Search in Google Scholar

[9] S. Fujita, C. Magnant and K. Ozeki, Rainbow generalizations of Ramsey theory: a survey, Graphs Combin. 26 (2010) 1–30. https://doi.org/10.1007/s00373-010-0891-3 Search in Google Scholar

[10] J. Ivančo, M2-edge colorings of dense graphs, Opuscula Math. 36 (2016) 603–612. https://doi.org/10.7494/OpMath.2016.36.5.603 Search in Google Scholar

[11] T. Jiang, Edge-colorings with no large polychromatic stars, Graphs Combin. 18 (2002) 303–308. https://doi.org/10.1007/s003730200022 Search in Google Scholar

[12] T. Larjomma and A. Popa, The min-max edge q-coloring problem, J. Graph Algorithms Appl. 19 (2015) 505–528. https://doi.org/10.7155/jgaa.00373 Search in Google Scholar

[13] J.J. Montellano-Ballesteros, On totally multicolored stars, J. Graph Theory 51 (2006) 225–243. https://doi.org/10.1002/jgt.20140 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo