Maximum Edge-Colorings Of Graphs
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 col...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2016-02-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1843 |
| _version_ | 1797718002604441600 |
|---|---|
| author | Jendrol’ Stanislav Vrbjarová Michaela |
| author_facet | Jendrol’ Stanislav Vrbjarová Michaela |
| author_sort | Jendrol’ Stanislav |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-03-12T08:44:39Z |
| format | Article |
| id | doaj.art-2e5305cd9fd5496191862e94d946ad4d |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:44:39Z |
| publishDate | 2016-02-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-2e5305cd9fd5496191862e94d946ad4d2023-09-02T16:29:34ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922016-02-0136111712510.7151/dmgt.1843dmgt.1843Maximum Edge-Colorings Of GraphsJendrol’ Stanislav0Vrbjarová Michaela1Institute of Mathematics, P.J.Šafárik University, Jesenná 5 040 01 Košice SlovakiaInstitute of Mathematics, P.J.Šafárik University, Jesenná 5 040 01 Košice SlovakiaAn 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.https://doi.org/10.7151/dmgt.1843edge-coloringr-maximum k-edge-coloringunique-maximum edge-coloringweak-odd edge-coloringweak-even edge-coloring05c1505c35 |
| spellingShingle | Jendrol’ Stanislav Vrbjarová Michaela Maximum Edge-Colorings Of Graphs Discussiones Mathematicae Graph Theory edge-coloring r-maximum k-edge-coloring unique-maximum edge-coloring weak-odd edge-coloring weak-even edge-coloring 05c15 05c35 |
| title | Maximum Edge-Colorings Of Graphs |
| title_full | Maximum Edge-Colorings Of Graphs |
| title_fullStr | Maximum Edge-Colorings Of Graphs |
| title_full_unstemmed | Maximum Edge-Colorings Of Graphs |
| title_short | Maximum Edge-Colorings Of Graphs |
| title_sort | maximum edge colorings of graphs |
| topic | edge-coloring r-maximum k-edge-coloring unique-maximum edge-coloring weak-odd edge-coloring weak-even edge-coloring 05c15 05c35 |
| url | https://doi.org/10.7151/dmgt.1843 |
| work_keys_str_mv | AT jendrolstanislav maximumedgecoloringsofgraphs AT vrbjarovamichaela maximumedgecoloringsofgraphs |