On Sylvester colorings of cubic graphs

zbMATH Open1405.05061arXiv1511.02475MaRDI QIDQ4622633FDOQ4622633

Authors: Anush Hakobyan, Vahan V. Mkrtchyan 

Publication date: 13 February 2019

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 states that for any bridgeless cubic graph $G$, one has: $PprecG$. The second author has recently introduced the Sylvester coloring conjecture, which states that for any cubic graph $G$ one has: $SprecG$. Here $S$ is the Sylvester graph on $10$ vertices. In this paper, we prove the analogue of Sylvester coloring conjecture for cubic pseudo-graphs. Moreover, we show that if $G$ is any connected simple cubic graph $G$ with $GprecP$, then $G=P$. This implies that the Petersen graph does not admit an $S_{16}$-coloring, where $S_{16}$ is the smallest connected simple cubic graph without a perfect matching. $S_{16}$ has $16$ vertices. %We conjecture that there are infinitely many connected cubic simple graphs which do not admit an %$S_{16}$-coloring. Finally, we obtain $2$ results towards the Sylvester coloring conjecture. The first result states that any cubic graph $G$ has a coloring with edges of Sylvester graph $S$ such that at least $frac45$ of vertices of $G$ meet the conditions of Sylvester coloring conjecture. The second result states that any claw-free cubic graph graph admits an $S$-coloring. This results is an application of our result on cubic pseudo-graphs.

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

Recommendations

• A remark on the Petersen coloring conjecture of Jaeger
• \(S_{12}\) and \(P_{12}\)-colorings of cubic graphs
• Variations on the Petersen colouring conjecture
• New approach to Petersen coloring
• Normal 6-edge-colorings of some bridgeless cubic graphs

zbMATH Keywords

Sylvester coloring conjecturePetersen coloring conjecture of Jaeger states

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

• Matching theory
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The structure of claw-free graphs
• Classification and characterizations of snarks
• Measurements of edge-uncolorability
• 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 parsimonious edge-colouring of graphs with maximum degree three
• Perfect matchings in claw-free cubic graphs
• A remark on the Petersen coloring conjecture of Jaeger

Cited In (5)

• A generalization of Tait coloring cubic graphs
• A remark on the Petersen coloring conjecture of Jaeger
• \(S_{12}\) and \(P_{12}\)-colorings of cubic graphs
• 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

This page was built for publication: On Sylvester colorings of cubic graphs

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