| Tartalom: |
http://real.mtak.hu/44501/ |
| Archívum: |
MTA Könyvtár |
| Gyűjtemény: |
Status = Published
Type = Article
|
| Cím: |
When the vertex coloring of a graph is an edge coloring of its line graph - a rare coincidence
|
| Létrehozó: |
Bujtás, Csilla
Sampathkumar, E.
Tuza, Zsolt
Dominic, C.
Pushpalatha, L
|
| Dátum: |
2016
|
| Téma: |
QA Mathematics / matematika
QA166-QA166.245 Graphs theory / gráfelmélet
|
| Tartalmi leírás: |
The 3-consecutive vertex coloring number psi(3c)(G) of a graph G is the maximum number of colors permitted in a coloring of the vertices of G such that the middle vertex of any path P-3 subset of G has the same color as one of the ends of that P-3. This coloring constraint exactly means that no P-3 subgraph of G is properly colored in the classical sense. The 3-consecutive edge coloring number psi(3c)'(G) is the maximum number of colors permitted in a coloring of the edges of G such that the middle edge of any sequence of three edges (in a path P-4 or cycle C-3) has the same color as one of the other two edges. For graphs G of minimum degree at least 2, denoting by L(G) the line graph of G, we prove that there is a bijection between the 3-consecutive vertex colorings of G and the 3-consecutive edge colorings of L(G), which keeps the number of colors unchanged, too. This implies that psi(3c)(G) = psi(3c)'(L(G)); i.e., the situation is just the opposite of what one would expect for first sight.
|
| Nyelv: |
angol
|
| Típus: |
Article
PeerReviewed
info:eu-repo/semantics/article
|
| Formátum: |
text
|
| Azonosító: |
Bujtás, Csilla and Sampathkumar, E. and Tuza, Zsolt and Dominic, C. and Pushpalatha, L (2016) When the vertex coloring of a graph is an edge coloring of its line graph - a rare coincidence. ARS COMBINATORIA, 128. pp. 165-173. ISSN 0381-7032
|
| Kapcsolat: |
MTMT:3127317
|
