Normal 5-edge-coloring of some snarks superpositioned by the Petersen graph
| Autor: | Sedlar, Jelena, Škrekovski, Riste |
|---|---|
| Rok vydání: | 2023 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | In a (proper) edge-coloring of a bridgeless cubic graph G an edge e is rich (resp. poor) if the number of colors of all edges incident to end-vertices of e is 5 (resp. 3). An edge-coloring of G is is normal if every edge of G is either rich or poor. In this paper we consider snarks ~G obtained by a simple superposition of edges and vertices of a cycle C in a snark G: For an even cycle C we show that a normal coloring of G can be extended to a normal coloring of ~G without changing colors of edges outside C in G: An interesting remark is that this is in general impossible for odd cycles, since the normal coloring of a Petersen graph P10 cannot be extended to a superposition of P10 on a 5-cycle without changing colors outside the 5-cycle. On the other hand, as our colorings of the superpositioned snarks introduce 18 or more poor edges, we are inclined to believe that every bridgeless cubic graph istinct from P10 has a normal coloring with at least one poor edge and possibly with at least 6 if we also exclude the Petersen graph with one vertex truncated. Comment: 20 pages, 11 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|