✦ LIBER ✦

Packing Odd Circuits in Eulerian Graphs

✍ Scribed by James F. Geelen; Bertrand Guenin

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 179 KB
Volume: 86
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.2002.2128

No coin nor oath required. For personal study only.

✦ Synopsis

Let C be the clutter of odd circuits of a signed graph ðG; SÞ: For nonnegative integral edge-weights w; we are interested in the linear program minðw t x: xðCÞ51; for C 2 C; and x50Þ; which we denote by (P). The problem of solving the related integer program clearly contains the maximum cut problem, which is NP-hard. Guenin proved that (P) has an optimal solution that is integral so long as ðG; SÞ does not contain a minor isomorphic to odd-K 5 : We generalize this by showing that if ðG; SÞ does not contain a minor isomorphic to odd-K 5 then (P) has an integral optimal solution and its dual has a half-integral optimal solution.

📜 SIMILAR VOLUMES

Circuit Decompositions of Eulerian Graph

Circuit Decompositions of Eulerian Graphs

✍ Genghua Fan; Cun-Quan Zhang 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 312 KB

Parity equivalence in eulerian graphs

✍ Sabidussi, Gert 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB 👁 2 views

Given a connected eulerian graph, we consider the question-related to the factorisation of regular graphs of even degree-under what conditions the distance of two edges e, e in an eulerian walk (i.e., the number of edges intervening between e and e ) always is of the same parity. A characterisation

Packing Cycles in Graphs

✍ Guoli Ding; Wenan Zang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 267 KB

Odd Wheels in Graphs

✍ Baoguang Xu; Guoping Jin; Zhenhong Liu 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 115 KB

For k \ 1 the odd wheel of 2k+1 spokes, denoted by W 2k+1 , is the graph obtained from a cycle of length 2k+1 by adding a new vertex and joining it to all vertices of the cycle. In this paper it is shown that if a graph G of order n with minimum degree greater than 7n/12 is at least 4-chromatic then

Packing cuts in undirected graphs

✍ Alberto Caprara; Alessandro Panconesi; Romeo Rizzi 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 160 KB

Induced Circuits in Planar Graphs

✍ C. Mcdiarmid; B. Reed; A. Schrijver; B. Shepherd 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 291 KB