DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume

Authors:

J. Ivančo

Jaroslav Ivančo

Institute of MathematicsP.J.Š. University, Jesenná 5SK-041 54 Košice SLOVAK REPUBLIC

email: jaroslav.ivanco@upjs.sk

A. Onderko

Alfred Onderko

Institute of Mathematics, P. J.Safarik University

email: alfred.onderko@student.upjs.sk

Title:

On $\mathrm M_f$-edge colorings of graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 42(4) (2022) 1075-1088

Received: 2019-12-03 , Revised: 2020-04-30 , Accepted: 2020-04-30 , Available online: 2020-05-25 , https://doi.org/10.7151/dmgt.2329

Abstract:

An edge coloring $\varphi$ of a graph $G$ is called an $\mathrm M_f$-edge coloring if $|\varphi(v)|\leq f(v)$ for every vertex $v$ of $G$, where $\varphi(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 $\mathcal K_f(G)$ denote the maximum number of colors used in an $\mathrm M_f$-edge coloring of $G$. In this paper we establish some bounds on $\mathcal K_f(G)$, present some graphs achieving the bounds and determine exact values of $\mathcal K_f(G)$ for some special classes of graphs.

Keywords:

edge coloring, anti-Ramsey number, dominating set

References:

  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
  2. S. Akbari, N. Alipourfard, P. Jandaghi and M. Mirtaheri, On $N_2$-vertex coloring of graphs, Discrete Math. Algorithms Appl. 10 (2018) 1850007.
    https://doi.org/10.1142/S1793830918500076
  3. K. Budajová and J. Czap, $\mathrm M_2$-edge coloring and maximum matching of graphs, Int. J. Pure Appl. Math. 88 (2013) 161–167.
    https://doi.org/10.12732/ijpam.v88i2.1
  4. J. Czap, $\mathrm M_i$-edge colorings of graphs, Appl. Math. Sci. 5 (2011) 2437–2442.
  5. J. Czap, A note on $\mathrm M_2$-edge colorings of graphs, Opuscula Math. 35 (2015) 287–291.
    https://doi.org/10.7494/OpMath.2015.35.3.287
  6. J. Czap and P. Šugerek, $\mathrm M_i$-edge colorings of complete graphs, Appl. Math. Sci. 9 (2015) 3835–3842.
    https://doi.org/10.12988/ams.2015.53264
  7. J. Czap, P. Šugerek and J. Ivančo, $\mathrm M_2$-edge colorings of cacti and graph joins, Discuss. Math. Graph Theory 36 (2016) 59–69.
    https://doi.org/10.7151/dmgt.1842
  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
  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
  10. J. Ivančo, $\mathrm M_2$-edge colorings of dense graphs, Opuscula Math. 36 (2016) 603–612.
    https://doi.org/10.7494/OpMath.2016.36.5.603
  11. T. Jiang, Edge-colorings with no large polychromatic stars, Graphs Combin. 18 (2002) 303–308.
    https://doi.org/10.1007/s003730200022
  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
  13. J.J. Montellano-Ballesteros, On totally multicolored stars, J. Graph Theory 51 (2006) 225–243.
    https://doi.org/10.1002/jgt.20140
Close