S₁₂ and P₁₂-colorings of cubic graphs

DOI10.26493/1855-3974.1758.410zbMATH Open1435.05076arXiv1807.08138OpenAlexW2987876456MaRDI QIDQ5217082FDOQ5217082

Authors: Anush Hakobyan, Vahan V. Mkrtchyan 

Publication date: 21 February 2020

Published in: Ars Mathematica Contemporanea (Search for Journal in Brave)

Abstract: If $G$ and $H$ are two cubic graphs, then an $H$-coloring of $G$ is a proper edge-coloring $f$ with edges of $H$, such that for each vertex $x$ of $G$, there is a vertex $y$ of $H$ with $f(partia{l}_G(x))=partia{l}_H(y)$. If $G$ admits an $H$-coloring, then we will write $HprecG$. The Petersen coloring conjecture of Jaeger ($P_{10}$-conjecture) states that for any bridgeless cubic graph $G$, one has: $P_{10}precG$. The Sylvester coloring conjecture ($S_{10}$-conjecture) states that for any cubic graph $G$, $S_{10}precG$. In this paper, we introduce two new conjectures that are related to these conjectures. The first of them states that any cubic graph with a perfect matching admits an $S_{12}$-coloring. The second one states that any cubic graph $G$ whose edge-set can be covered with four perfect matchings, admits a $P_{12}$-coloring. We call these new conjectures $S_{12}$-conjecture and $P_{12}$-conjecture, respectively. Our first results justify the choice of graphs in $S_{12}$-conjecture and $P_{12}$-conjecture. Next, we characterize the edges of $P_{12}$ that may be fictive in a $P_{12}$-coloring of a cubic graph $G$. Finally, we relate the new conjectures to the already known conjectures by proving that $S_{12}$-conjecture implies $S_{10}$-conjecture, and $P_{12}$-conjecture and $(5,2)$-Cycle cover conjecture together imply $P_{10}$-conjecture. Our main tool for proving the latter statement is a new reformulation of $(5,2)$-Cycle cover conjecture, which states that the edge-set of any claw-free bridgeless cubic graph can be covered with four perfect matchings.

Full work available at URL: https://arxiv.org/abs/1807.08138

Recommendations

• Two-coloring the edges of a cubic graph such that each monochromatic component is a path of length at most 5
• A remark on the Petersen coloring conjecture of Jaeger
• Normal edge-colorings of cubic graphs
• Partially normal 5-edge-colorings of cubic graphs
• On Sylvester colorings of cubic graphs

zbMATH Keywords

cubic graphPetersen graphPetersen coloring conjecture\(S_{10}\)-conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• The NP-Completeness of Edge-Coloring
• Title not available (Why is that?)
• The structure of claw-free graphs
• Title not available (Why is that?)
• Blocking and anti-blocking pairs of polyhedra
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings
• Perfect matchings in claw-free cubic graphs
• Title not available (Why is that?)
• On perfect matching coverings and even subgraph coverings
• A remark on the Petersen coloring conjecture of Jaeger
• Cycle-continuous mappings -- order structure
• On Sylvester Colorings of Cubic Graphs

Cited In (7)

• \(H\)-colorings for 4-regular graphs
• Ban–Linial's Conjecture and treelike snarks
• A remark on the Petersen coloring conjecture of Jaeger
• Variations on the Petersen colouring conjecture
• On the existence of graphs which can colour every regular graph
• Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching
• An equivalent formulation of the Fan-Raspaud Conjecture and related problems

This page was built for publication: \(S_{12}\) and \(P_{12}\)-colorings of cubic graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5217082)