Even-cycle decompositions of graphs with no odd-K₄-minor

DOI10.1016/J.EJC.2017.04.010MaRDI QIDQ2400967zbMATH OpenOpenAlexWikidataFDO

Authors Tony Huynh, Sang-Il Oum, Maryam Verdian-Rizi

Publication date 31 August 2017

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

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

zbMATH Keywords

Eulerian bipartite graph

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Abstract: An even-cycle decomposition of a graph G is a partition of E(G) into cycles of even length. Evidently, every Eulerian bipartite graph has an even-cycle decomposition. Seymour (1981) proved that every 2-connected loopless Eulerian planar graph with an even number of edges also admits an even-cycle decomposition. Later, Zhang (1994) generalized this to graphs with no $K_5$-minor. Our main theorem gives sufficient conditions for the existence of even-cycle decompositions of graphs in the absence of odd minors. Namely, we prove that every 2-connected loopless Eulerian odd-$K_4$-minor-free graph with an even number of edges has an even-cycle decomposition. This is best possible in the sense that `odd-$K_4$-minor-free' cannot be replaced with `odd-$K_5$-minor-free.' The main technical ingredient is a structural characterization of the class of odd-$K_4$-minor-free graphs, which is due to Lov'asz, Seymour, Schrijver, and Truemper.

Recommendations

• On even circuit decompositions of eulerian graphs
• scientific article; zbMATH DE number 2061806
• On 4-connected graphs without even cycle decompositions
• Even cycle decompositions of 4-regular graphs and line graphs
• On 4-connected 4-regular graphs without even cycle decompositions

Cites work

• scientific article; zbMATH DE number 446493 (Why is no real title available?)
• scientific article; zbMATH DE number 49899 (Why is no real title available?)
• scientific article; zbMATH DE number 1021588 (Why is no real title available?)
• (Some of) the many uses of Eulerian graphs in graph theory (plus some applications)
• A characterization of weakly bipartite graphs
• A decomposition of the matroids with the max-flow min-cut property
• Addendum to ``A decomposition of the matroids with the max-flow min-cut property
• Decomposition of regular matroids
• Even circuits in planar graphs
• Even cycles in graphs
• Every planar map is four colorable
• Homomorphisms of planar signed graphs to signed projective cubes
• On even circuit decompositions of eulerian graphs
• Signed graphs
• Weakly bipartite graphs and the max-cut problem

Cited in

(12)

• On 4-connected graphs without even cycle decompositions
• Cycle intersection graphs and minimum decycling sets of even graphs
• Minimal regular graphs with every edge in a triangle
• Negative (and positive) circles in signed graphs: a problem collection
• On 4-connected 4-regular graphs without even cycle decompositions
• On even cycle decompositions of line graphs of cubic graphs
• Strongly even-cycle decomposable graphs
• Strongly even cycle decomposable 4-regular line graphs
• scientific article; zbMATH DE number 2061806 (Why is no real title available?)
• Strongly even cycle decomposable non-planar line graphs
• Improper colouring of graphs with no odd clique minor
• Compatible cycle decomposition of bad K₅-minor-free graphs

This page was built for publication: Even-cycle decompositions of graphs with no odd-\(K_4\)-minor

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