**Reference**:- Erik D. Demaine, MohammadTaghi Hajiaghayi, and Ken-ichi Kawarabayashi, “Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs”, in
*Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010)*, Austin, Texas, January 17–19, 2010, pages 329–344. **Abstract**:-
We prove two structural decomposition theorems about graphs excluding a fixed
odd minor
*H*, and show how these theorems can be used to obtain approximation algorithms for several algorithmic problems in such graphs. Our decomposition results provide new structural insights into odd-*H*-minor-free graphs, on the one hand generalizing the central structural result from Graph Minor Theory, and on the other hand providing an algorithmic decomposition into two bounded-treewidth graphs, generalizing a similar result for minors. As one example of how these structural results conquer difficult problems, we obtain a polynomial-time 2-approximation for vertex coloring in odd-*H*-minor-free graphs, improving on the previous*O*(|*V*(*H*)|)-approximation for such graphs and generalizing the previous 2-approximation for*H*-minor-free graphs. The class of odd-*H*-minor-free graphs is a vast generalization of the well-studied*H*-minor-free graph families and includes, for example, all bipartite graphs plus a bounded number of apices. Odd-*H*-minor-free graphs are particularly interesting from a structural graph theory perspective because they break away from the sparsity of*H*-minor-free graphs, permitting a quadratic number of edges. **Availability**:- The paper is available in PostScript (405k), gzipped PostScript (141k), and PDF (288k).
- See information on file formats.
- [Google Scholar search]

See also other papers by Erik Demaine.

Last updated June 13, 2024 by Erik Demaine.