A remark on the Petersen coloring conjecture of Jaeger

MaRDI QIDQ2848732zbMATH OpenFDO

Authors Vahan V. Mkrtchyan

Publication date 26 September 2013

Published in The Australasian Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

cubic graphsPetersen coloring conjectureSylvester coloring conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: If $G$ and $H$ are two cubic graphs, then we write $HprecG$, if $G$ admits 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)$. Let $P$ and $S$ be the Petersen graph and the Sylvester graph, respectively. In this paper, we introduce the Sylvester coloring conjecture. Moreover, we show that if $G$ is a connected bridgeless cubic graph with $GprecP$, then $G=P$. Finally, if $G$ is a connected cubic graph with $GprecS$, then $G=S$.

Recommendations

• On Sylvester colorings of cubic graphs
• New approach to Petersen coloring
• Variations on the Petersen colouring conjecture
• \(S_{12}\) and \(P_{12}\)-colorings of cubic graphs
• On sublinear approximations for the Petersen coloring conjecture

Cited in

(14)

• On the existence of graphs which can colour every regular graph
• Normal 5-edge-coloring of some snarks superpositioned by flower snarks
• Variations on the Petersen colouring conjecture
• \(H\)-colorings for 4-regular graphs
• Normal 6-edge-colorings of some bridgeless cubic graphs
• On Sylvester colorings of cubic graphs
• Normal 5-edge-colorings of a family of Loupekhine snarks
• An equivalent formulation of the Fan-Raspaud conjecture and related problems
• On \(\mathbb{Z}\)-flow-continuous maps and oriented colorings of cubic graphs
• Petersen-colorings and some families of snarks
• Measures of edge-uncolorability of cubic graphs
• On a conjecture concerning the Petersen graph
• Disjoint odd circuits in a bridgeless cubic graph can be quelled by a single perfect matching
• \(S_{12}\) and \(P_{12}\)-colorings of cubic graphs

This page was built for publication: A remark on the Petersen coloring conjecture of Jaeger

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