PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2016 | 36 | 1 | 117-125
Tytuł artykułu

Maximum Edge-Colorings Of Graphs

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Rocznik
Tom
36
Numer
1
Strony
117-125
Opis fizyczny
Daty
wydano
2016-02-01
otrzymano
2015-01-20
poprawiono
2015-05-11
zaakceptowano
2015-05-11
online
2016-01-19
Twórcy
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.
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1843
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.