Normal 5-edge-coloring of some snarks superpositioned by the Petersen graph

Jelena Sedlar and Riste Škrekovski

Applied Mathematics and Computation, 2024, vol. 467, issue C

Abstract: 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 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 distinct 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 being truncated.

Keywords: Normal edge-coloring; Cubic graph; Snark; Superposition; Petersen coloring conjecture (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300323006628
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:467:y:2024:i:c:s0096300323006628

DOI: 10.1016/j.amc.2023.128493

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().