Petersen cores and the oddness of cubic graphs

DOI10.1002/JGT.22014MaRDI QIDQ2958201zbMATH OpenOpenAlexFDO

Authors Eckhard Steffen, Li-Gang Jin

Publication date 1 February 2017

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

perfect matchingscubic graphsoddnesssnarkscovers

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: Let $G$ be a bridgeless cubic graph. Consider a list of $k$ 1-factors of $G$. Let $E_i$ be the set of edges contained in precisely $i$ members of the $k$ 1-factors. Let $m{u}_k(G)$ be the smallest $|E_0|$ over all lists of $k$ 1-factors of $G$. If $G$ is not 3-edge-colorable, then $m{u}_3(G)geq3$. In [E. Steffen, 1-factor and cycle covers of cubic graphs, J. Graph Theory 78(3) (2015) 195-206] it is shown that if $m{u}_3(G)ot=0$, then $2m{u}_3(G)$ is an upper bound for the girth of $G$. We show that $m{u}_3(G)$ bounds the oddness $omega(G)$ of $G$ as well. We prove that $omega(G)leqfrac23m{u}_3(G)$. If $m{u}_3(G)=frac23m{u}_3(G)$, then every $m{u}_3(G)$-core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4-edge-connected cubic graph $G$ with $omega(G)=frac23m{u}_3(G)$. On the other hand, the difference between $omega(G)$ and $frac23m{u}_3(G)$ can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer $kgeq3$, there exists a bridgeless cubic graph $G$ such that $m{u}_3(G)=k$.

Recommendations

• 1-factor and cycle covers of cubic graphs
• Small snarks with large oddness
• Oddness to resistance ratios in cubic graphs
• Weak oddness as an approximation of oddness and resistance in cubic graphs
• Circular edge-colorings of cubic graphs with girth six

Cites work

• 1-factor and cycle covers of cubic graphs
• Classification and characterizations of snarks
• Construction of class two graphs with maximum vertex degree three
• Decomposition of snarks
• Decompositions and reductions of snarks
• Fulkerson's conjecture and circuit covers
• Girths of bipartite sextet graphs
• Infinite Families of Nontrivial Trivalent Graphs Which are Not Tait Colorable
• Intersecting 1-factors and nowhere-zero 5-flows
• On snarks that are far from being 3-edge colorable
• Sparsely intersecting perfect matchings in cubic graphs

Cited in

(8)

• The smallest nontrivial snarks of oddness 4
• Partially normal 5-edge-colorings of cubic graphs
• Cores, joins and the Fano-flow conjectures
• Weak oddness as an approximation of oddness and resistance in cubic graphs
• An equivalent formulation of the Fan-Raspaud conjecture and related problems
• Cubic graphs with colouring defect 3
• Measures of edge-uncolorability of cubic graphs
• Girth, oddness, and colouring defect of snarks

This page was built for publication: Petersen cores and the oddness of cubic graphs

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