Normal 6-edge-colorings of cubic graphs with oddness 2
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914010972028928 |
|---|---|
| author | Fabrici, Igor Lužar, Borut Soták, Roman Švecová, Diana |
| author_facet | Fabrici, Igor Lužar, Borut Soták, Roman Švecová, Diana |
| contents | A normal edge-coloring of a cubic graph is a proper edge-coloring, in which every edge is adjacent to edges colored with four distinct colors or to edges colored with two distinct colors. It is conjectured that $5$ colors suffice for a normal edge-coloring of any bridgeless cubic graph and this statement is equivalent to the Petersen Coloring Conjecture.
In this paper, we extend the result of Mazzuoccolo and Mkrtchyan (Normal 6-edge-colorings of some bridgeless cubic graphs, Discrete Appl. Math. 277 (2020), 252--262), who proved that every cycle permutation graph admits a normal edge-coloring with at most $6$ colors. In particular, we show that every cubic graph with oddness $2$ admits a normal edge-coloring with at most $6$ colors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20565 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Normal 6-edge-colorings of cubic graphs with oddness 2 Fabrici, Igor Lužar, Borut Soták, Roman Švecová, Diana Combinatorics 05C15 A normal edge-coloring of a cubic graph is a proper edge-coloring, in which every edge is adjacent to edges colored with four distinct colors or to edges colored with two distinct colors. It is conjectured that $5$ colors suffice for a normal edge-coloring of any bridgeless cubic graph and this statement is equivalent to the Petersen Coloring Conjecture. In this paper, we extend the result of Mazzuoccolo and Mkrtchyan (Normal 6-edge-colorings of some bridgeless cubic graphs, Discrete Appl. Math. 277 (2020), 252--262), who proved that every cycle permutation graph admits a normal edge-coloring with at most $6$ colors. In particular, we show that every cubic graph with oddness $2$ admits a normal edge-coloring with at most $6$ colors. |
| title | Normal 6-edge-colorings of cubic graphs with oddness 2 |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2508.20565 |