Packing odd circuits
SIAM Journal on Discrete Mathematics , Volume 21 p. 273- 302
We determine the structure of a class of graphs that do not contain the complete graph on ﬁve vertices as a “signed minor.” The result says that each graph in this class can be decomposed into elementary building blocks in which maximum packings by odd circuits can be found by ﬂow or matching techniques. This allows us to actually ﬁnd a largest collection of pairwise edge disjoint odd circuits in polynomial time (for general graphs this is NP-hard). Furthermore it provides an algorithm to test membership of our class of graphs.
|odd circuits, packing, excluded minors, decomposition, signed graphs|
|Signed and weighted graphs (msc 05C22), Factorization, matching, partitioning, covering and packing (msc 05C70), Structural characterization of families of graphs (msc 05C75), Graph minors (msc 05C83), Combinatorial optimization (msc 90C27)|
|SIAM Journal on Discrete Mathematics|
|Organisation||Probability, Networks and Algorithms|
Conforti, M, & Gerards, A.M.H. (2007). Packing odd circuits. SIAM Journal on Discrete Mathematics, 21, 273–302.