Maximum Edge-Colorings Of Graphs

• Autorzy: Stanislav Jendrol’ , Michaela Vrbjarová
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

edge-coloring; r-maximum k-edge-coloring; unique-maximum edge-coloring; weak-odd edge-coloring; weak-even edge-coloring

Kategorie tematyczne

• 05C15: Coloring of graphs and hypergraphs
• 05C35: Extremal problems

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2016
• Tom: 36
• Numer: 1
• Strony: 117-125

Daty

wydano

2016-02-01

otrzymano

2015-01-20

poprawiono

2015-05-11

zaakceptowano

2015-05-11

online

2016-01-19

Twórcy

autor

Stanislav Jendrol’

• Institute of Mathematics, P.J.Šafárik University, Jesenná 5 040 01 Košice Slovakia

autor

Michaela Vrbjarová

• Institute of Mathematics, P.J.Šafárik University, Jesenná 5 040 01 Košice Slovakia

Bibliografia

• [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]
• [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]
• [6] B. Lužar, M. Petruševski and R.Škrekovski, Odd edge-coloring of graphs, Ars Math. Contemp. 9 (2015) 277–287.
• [7] B. Lužar, M. Petruševski and R.Škrekovski, Weak-parity edge-colorings of graphs, manuscript, 2014.[WoS]
• [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.

Identyfikatory

DOI

10.7151/dmgt.1843