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

DOI10.26493/1855-3974.1758.410MaRDI QIDQ5217082zbMATH OpenOpenAlexFDO

Authors Anush Hakobyan, Vahan V. Mkrtchyan

Publication date 21 February 2020

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

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3952799 (Why is no real title available?)
• scientific article; zbMATH DE number 4075098 (Why is no real title available?)
• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• A remark on the Petersen coloring conjecture of Jaeger
• Blocking and anti-blocking pairs of polyhedra
• On Multi-Colourings of Cubic Graphs, and Conjectures of Fulkerson and Tutte
• On Sylvester colorings of cubic graphs
• On perfect matching coverings and even subgraph coverings
• Perfect matchings in claw-free cubic graphs
• The NP-Completeness of Edge-Coloring
• The structure of claw-free graphs

Cited in

(9)

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

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)