Maximum Edge-Colorings Of Graphs

Stanislav Jendrol’; Michaela Vrbjarová

Discussiones Mathematicae Graph Theory (2016)

  • Volume: 36, Issue: 1, page 117-125
  • ISSN: 2083-5892

Abstract

top
An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) χ r ' ( G ) is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 χ r ' ( G ) ≤ 3 for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i χ 1 ' ( G ) = i , i = 1, 2, 3 are characterized. The precise value of the r-maximum index, r ≥ 1, is determined for trees and complete graphs.

How to cite

top

Stanislav Jendrol’, and Michaela Vrbjarová. "Maximum Edge-Colorings Of Graphs." Discussiones Mathematicae Graph Theory 36.1 (2016): 117-125. <http://eudml.org/doc/276973>.

@article{StanislavJendrol2016,
abstract = {An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) $\chi _r^\prime (G)$ is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 $\chi _r^\prime (G) \le 3$ for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i $\chi _1^\prime (G) = i$ , i = 1, 2, 3 are characterized. The precise value of the r-maximum index, r ≥ 1, is determined for trees and complete graphs.},
author = {Stanislav Jendrol’, Michaela Vrbjarová},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {edge-coloring; r-maximum k-edge-coloring; unique-maximum edge-coloring; weak-odd edge-coloring; weak-even edge-coloring; -maximum -edge-coloring},
language = {eng},
number = {1},
pages = {117-125},
title = {Maximum Edge-Colorings Of Graphs},
url = {http://eudml.org/doc/276973},
volume = {36},
year = {2016},
}

TY - JOUR
AU - Stanislav Jendrol’
AU - Michaela Vrbjarová
TI - Maximum Edge-Colorings Of Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2016
VL - 36
IS - 1
SP - 117
EP - 125
AB - An r-maximum k-edge-coloring of G is a k-edge-coloring of G having a property that for every vertex v of degree dG(v) = d, d ≥ r, the maximum color, that is present at vertex v, occurs at v exactly r times. The r-maximum index [...] χr′(G) $\chi _r^\prime (G)$ is defined to be the minimum number k of colors needed for an r-maximum k-edge-coloring of graph G. In this paper we show that [...] χr′(G)≤3 $\chi _r^\prime (G) \le 3$ for any nontrivial connected graph G and r = 1 or 2. The bound 3 is tight. All graphs G with [...] χ1′(G)=i $\chi _1^\prime (G) = i$ , i = 1, 2, 3 are characterized. The precise value of the r-maximum index, r ≥ 1, is determined for trees and complete graphs.
LA - eng
KW - edge-coloring; r-maximum k-edge-coloring; unique-maximum edge-coloring; weak-odd edge-coloring; weak-even edge-coloring; -maximum -edge-coloring
UR - http://eudml.org/doc/276973
ER -

References

top
  1. [1] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008). 
  2. [2] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs (Fifth edition) (Chapman & Hall, CRC, Boca Raton, 2011). 
  3. [3] P. Cheilaris, B. Keszegh and D. Pálvölgyi, Unique-maximum and conflict-free coloring for hypergraphs and tree graphs, SIAM J. Discrete Math. 27 (2013) 1775–1787. doi:10.1137/120880471[Crossref][WoS] Zbl1292.05107
  4. [4] P. Cheilaris and G. Tóth, Graph unique-maximum and conflict-free coloring, J. Discrete Algorithms 9 (2011) 241–251. doi:10.1016/j.jda.2011.03.005[Crossref] 
  5. [5] I. Fabrici, S. Jendrol’ and M. Vrbjarová, Unique-maximum edge-colouring of plane graphs with respect to faces, Discrete Appl. Math. 185 (2015) 239–243. doi:10.1016/j.dam.2014.12.002[Crossref][WoS] Zbl1311.05061
  6. [6] B. Lužar, M. Petruševski and R.Škrekovski, Odd edge-coloring of graphs, Ars Math. Contemp. 9 (2015) 277–287. Zbl1329.05115
  7. [7] B. Lužar, M. Petruševski and R.Škrekovski, Weak-parity edge-colorings of graphs, manuscript, 2014.[WoS] Zbl1329.05115
  8. [8] L. Pyber, Covering the edges of a graph by ..., in: Sets, Graphs and Numbers, Colloquia Math. Soc. János Bolyai 60 (1991) 583–610. Zbl0792.05110

NotesEmbed ?

top

You must be logged in to post comments.