Normal 5-edge-coloring of some snarks superpositioned by Flower snarks
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916343272439808 |
|---|---|
| author | Sedlar, Jelena Škrekovski, Riste |
| author_facet | Sedlar, Jelena Škrekovski, Riste |
| contents | An edge e is normal in a proper edge-coloring of a cubic graph G if the number of distinct colors on four edges incident to e is 2 or 4: A normal edge-coloring of G is a proper edge-coloring in which every edge of G is normal. The Petersen Coloring Conjecture is equivalent to stating that every bridgeless cubic graph has a normal 5-edge-coloring. Since every 3-edge-coloring of a cubic graph is trivially normal, it is suficient to consider only snarks to establish the conjecture. In this paper, we consider a class of superpositioned snarks obtained by choosing a cycle C in a snark G and superpositioning vertices of C by one of two simple supervertices and edges of C by superedges Hx;y, where H is any snark and x; y any pair of nonadjacent vertices of H: For such superpositioned snarks, two suficient conditions are given for the existence of a normal 5-edge-coloring. The first condition yields a normal 5-edge-coloring for all hypohamiltonian snarks used as superedges, but only for some of the possible ways of connecting them. In particular, since the Flower snarks are hypohamiltonian, this consequently yields a normal 5-edge-coloring for many snarks superpositioned by the Flower snarks. The second sufficient condition is more demanding, but its application yields a normal 5-edge-colorings for all superpositions by the Flower snarks. The same class of snarks is considered in [S. Liu, R.-X. Hao, C.-Q. Zhang, Berge{Fulkerson coloring for some families of superposition snarks, Eur. J. Comb. 96 (2021) 103344] for the Berge-Fulkerson conjecture. Since we established that this class has a Petersen coloring, this immediately yields the result of the above mentioned paper. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_13340 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Normal 5-edge-coloring of some snarks superpositioned by Flower snarks Sedlar, Jelena Škrekovski, Riste Combinatorics 05C15 An edge e is normal in a proper edge-coloring of a cubic graph G if the number of distinct colors on four edges incident to e is 2 or 4: A normal edge-coloring of G is a proper edge-coloring in which every edge of G is normal. The Petersen Coloring Conjecture is equivalent to stating that every bridgeless cubic graph has a normal 5-edge-coloring. Since every 3-edge-coloring of a cubic graph is trivially normal, it is suficient to consider only snarks to establish the conjecture. In this paper, we consider a class of superpositioned snarks obtained by choosing a cycle C in a snark G and superpositioning vertices of C by one of two simple supervertices and edges of C by superedges Hx;y, where H is any snark and x; y any pair of nonadjacent vertices of H: For such superpositioned snarks, two suficient conditions are given for the existence of a normal 5-edge-coloring. The first condition yields a normal 5-edge-coloring for all hypohamiltonian snarks used as superedges, but only for some of the possible ways of connecting them. In particular, since the Flower snarks are hypohamiltonian, this consequently yields a normal 5-edge-coloring for many snarks superpositioned by the Flower snarks. The second sufficient condition is more demanding, but its application yields a normal 5-edge-colorings for all superpositions by the Flower snarks. The same class of snarks is considered in [S. Liu, R.-X. Hao, C.-Q. Zhang, Berge{Fulkerson coloring for some families of superposition snarks, Eur. J. Comb. 96 (2021) 103344] for the Berge-Fulkerson conjecture. Since we established that this class has a Petersen coloring, this immediately yields the result of the above mentioned paper. |
| title | Normal 5-edge-coloring of some snarks superpositioned by Flower snarks |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2306.13340 |