Maximum Edge-Colorings Of Graphs
Stanislav Jendrol’ ; Michaela Vrbjarová
Discussiones Mathematicae Graph Theory, Tome 36 (2016), p. 117-125 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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.

Publié le : 2016-01-01
EUDML-ID : urn:eudml:doc:276973 
@article{bwmeta1.element.doi-10_7151_dmgt_1843,
     author = {Stanislav Jendrol' and Michaela Vrbjarov\'a},
     title = {Maximum Edge-Colorings Of Graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {36},
     year = {2016},
     pages = {117-125},
     zbl = {1329.05109},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1843}
}

Stanislav Jendrol’; Michaela Vrbjarová. Maximum Edge-Colorings Of Graphs. Discussiones Mathematicae Graph Theory, Tome 36 (2016) pp. 117-125. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1843/

[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] | Zbl 1292.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] | Zbl 1311.05061

[6] B. Lužar, M. Petruševski and R.Škrekovski, Odd edge-coloring of graphs, Ars Math. Contemp. 9 (2015) 277–287. | Zbl 1329.05115

[7] B. Lužar, M. Petruševski and R.Škrekovski, Weak-parity edge-colorings of graphs, manuscript, 2014.[WoS] | Zbl 1329.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. | Zbl 0792.05110