Maximum Edge-Colorings Of Graphs
Stanislav Jendrol’; Michaela Vrbjarová
Discussiones Mathematicae Graph Theory (2016)
- Volume: 36, Issue: 1, page 117-125
- ISSN: 2083-5892
Access Full Article
top
Abstract
topHow to cite
topStanislav 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] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).
- [2] G. Chartrand, L. Lesniak and P. Zhang, Graphs & Digraphs (Fifth edition) (Chapman & Hall, CRC, Boca Raton, 2011).
- [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] 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] 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] B. Lužar, M. Petruševski and R.Škrekovski, Odd edge-coloring of graphs, Ars Math. Contemp. 9 (2015) 277–287. Zbl1329.05115
- [7] B. Lužar, M. Petruševski and R.Škrekovski, Weak-parity edge-colorings of graphs, manuscript, 2014.[WoS] Zbl1329.05115
- [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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.