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

Cited 3 time in webofscience Cited 0 time in scopus
  • Hit : 295
  • Download : 0
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 Lovasz, Seymour, Schrijver, and Truemper. (C) 2017 Elsevier Ltd. All rights reserved.
Publisher
ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD
Issue Date
2017-10
Language
English
Article Type
Article
Citation

EUROPEAN JOURNAL OF COMBINATORICS, v.65, pp.1 - 14

ISSN
0195-6698
DOI
10.1016/j.ejc.2017.04.010
URI
http://hdl.handle.net/10203/226118
Appears in Collection
MA-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 3 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0