Petersen cores and the oddness of cubic graphs

DOI10.1002/JGT.22014zbMATH Open1354.05113arXiv1501.00860OpenAlexW1682509088MaRDI QIDQ2958201FDOQ2958201

Authors: Eckhard Steffen, Li-Gang Jin 

Publication date: 1 February 2017

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

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$.

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

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

zbMATH Keywords

perfect matchingscubic graphsoddnesssnarkscovers

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (7)

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

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)