Cycle double covers and the semi-Kotzig frame

DOI10.1016/J.EJC.2011.12.001zbMATH Open1239.05077arXiv1105.5190OpenAlexW1986083510MaRDI QIDQ412256FDOQ412256

Dong Ye, Cun-Quan Zhang

Publication date: 4 May 2012

Published in: European Journal of Combinatorics (Search for Journal in Brave)

Abstract: Let $H$ be a cubic graph admitting a 3-edge-coloring $c:E(H)omathbb{Z}_3$ such that the edges colored by 0 and $muin1,2$ induce a Hamilton circuit of $H$ and the edges colored by 1 and 2 induce a 2-factor $F$. The graph $H$ is semi-Kotzig if switching colors of edges in any even subgraph of $F$ yields a new 3-edge-coloring of $H$ having the same property as $c$. A spanning subgraph $H$ of a cubic graph $G$ is called a {em semi-Kotzig frame} if the contracted graph $G/H$ is even and every non-circuit component of $H$ is a subdivision of a semi-Kotzig graph. In this paper, we show that a cubic graph $G$ has a circuit double cover if it has a semi-Kotzig frame with at most one non-circuit component. Our result generalizes some results of Goddyn (1988), and H"{a}ggkvist and Markstr"{o}m [J. Combin. Theory Ser. B (2006)].

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

zbMATH Keywords

semi-Kotzig frame

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the Problem of Decomposing a Graph into n Connected Factors
• Edge-Disjoint Spanning Trees of Finite Graphs
• Maximum matching and a polyhedron with 0,1-vertices
• Double covers of cubic graphs with oddness 4
• Five cycle double covers of some cubic graphs
• Polyhedral decompositions of cubic graphs
• On cycle-double covers of graphs of small oddness
• Cycle double covers of graphs with Hamilton paths
• Graphs with the Circuit Cover Property
• Semi-duality and the cycle double cover conjecture
• Cycle double covers and spanning minors. I
• Cycle double covers and spanning minors. II
• On the asymptotics of nodes of \(L^ 2\)-solutions of Schrödinger equations in dimensions \(\geq 3\)
• Kotzig frames and circuit double covers

Cited In (5)

• Kotzig frames and circuit double covers
• Cycle double covers via kotzig graphs
• Circuit Double Covers of Graphs
• Multicover Ucycles
• Circuit extension and circuit double cover of graphs

Recommendations

• STACS 2005 👍 👎
• Covering odd cycles 👍 👎
• Cycle double covers via kotzig graphs 👍 👎
• Cycle double covers and non-separating cycles 👍 👎
• Cycles of covers 👍 👎
• Kotzig frames and circuit double covers 👍 👎
• Signed cycle double covers 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Cycle double covers and the semi-Kotzig frame

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