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

DOI10.1016/J.EJC.2017.04.010zbMATH Open1369.05172arXiv1211.1868OpenAlexW2126192783WikidataQ114184788 ScholiaQ114184788MaRDI QIDQ2400967FDOQ2400967

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)

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.

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

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

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)

Cites Work

• Decomposition of regular matroids
• Signed graphs
• Every planar map is four colorable
• Title not available (Why is that?)
• A characterization of weakly bipartite graphs
• Weakly bipartite graphs and the max-cut problem
• Even circuits in planar graphs
• On even circuit decompositions of eulerian graphs
• Title not available (Why is that?)
• (Some of) the many uses of Eulerian graphs in graph theory (plus some applications)
• Title not available (Why is that?)
• Homomorphisms of planar signed graphs to signed projective cubes
• A decomposition of the matroids with the max-flow min-cut property
• Even cycles in graphs
• Addendum to ``A decomposition of the matroids with the max-flow min-cut property

Cited In (12)

• 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
• Title not available (Why is that?)
• Strongly even cycle decomposable non-planar line graphs
• Improper colouring of graphs with no odd clique minor
• Compatible cycle decomposition of bad \(K_5\)-minor-free graphs
• On 4-connected graphs without even cycle decompositions

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)