List strong and list normal edge-coloring of (sub)cubic graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917116630794240 |
|---|---|
| author | Lužar, Borut Máčajová, Edita Soták, Roman Švecová, Diana |
| author_facet | Lužar, Borut Máčajová, Edita Soták, Roman Švecová, Diana |
| contents | A strong edge-coloring of a graph is a proper edge-coloring, in which the edges of every path of length 3 receive distinct colors; in other words, every pair of edges at distance at most 2 must be colored differently. The least number of colors needed for a strong edge-coloring of a graph is the strong chromatic index. We consider the list version of the coloring and prove that the list strong chromatic index of graphs with maximum degree 3 is at most 10. This bound is tight and improves the previous bound of 11 colors.
We also consider the question whether the strong chromatic index and the list strong chromatic index always coincide. We answer it in negative by presenting an infinite family of graphs for which the two invariants differ. For the special case of the Petersen graph, we show that its list strong chromatic index equals 7, while its strong chromatic index is 5. Up to our best knowledge, this is the first known edge-coloring for which there are graphs with distinct values of the chromatic index and its list version.
In relation to the above, we also initiate the study of the list version of the normal edge-coloring. A normal edge-coloring of a cubic graph is a proper edge-coloring, in which every edge is adjacent to edges colored with 4 colors or to edges colored with 2 colors. It is conjectured that 5 colors suffice for a normal edge-coloring of any bridgeless cubic graph which is equivalent to the Petersen Coloring Conjecture.
Similarly to strong edge-coloring, list normal edge-coloring is much more restrictive and consequently for many graphs the list normal chromatic index is greater than the normal chromatic index. We show that there are cubic graphs with list normal chromatic index at least $9$, there are bridgeless cubic graphs with its value at least 8, and there are cyclically 4-edge-connected cubic graphs with value at least 7. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_01049 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | List strong and list normal edge-coloring of (sub)cubic graphs Lužar, Borut Máčajová, Edita Soták, Roman Švecová, Diana Combinatorics Discrete Mathematics 10C05 A strong edge-coloring of a graph is a proper edge-coloring, in which the edges of every path of length 3 receive distinct colors; in other words, every pair of edges at distance at most 2 must be colored differently. The least number of colors needed for a strong edge-coloring of a graph is the strong chromatic index. We consider the list version of the coloring and prove that the list strong chromatic index of graphs with maximum degree 3 is at most 10. This bound is tight and improves the previous bound of 11 colors. We also consider the question whether the strong chromatic index and the list strong chromatic index always coincide. We answer it in negative by presenting an infinite family of graphs for which the two invariants differ. For the special case of the Petersen graph, we show that its list strong chromatic index equals 7, while its strong chromatic index is 5. Up to our best knowledge, this is the first known edge-coloring for which there are graphs with distinct values of the chromatic index and its list version. In relation to the above, we also initiate the study of the list version of the normal edge-coloring. A normal edge-coloring of a cubic graph is a proper edge-coloring, in which every edge is adjacent to edges colored with 4 colors or to edges colored with 2 colors. It is conjectured that 5 colors suffice for a normal edge-coloring of any bridgeless cubic graph which is equivalent to the Petersen Coloring Conjecture. Similarly to strong edge-coloring, list normal edge-coloring is much more restrictive and consequently for many graphs the list normal chromatic index is greater than the normal chromatic index. We show that there are cubic graphs with list normal chromatic index at least $9$, there are bridgeless cubic graphs with its value at least 8, and there are cyclically 4-edge-connected cubic graphs with value at least 7. |
| title | List strong and list normal edge-coloring of (sub)cubic graphs |
| topic | Combinatorics Discrete Mathematics 10C05 |
| url | https://arxiv.org/abs/2410.01049 |