×

zbMATH — the first resource for mathematics

Even-hole-free graphs. I: Decomposition theorem. (English) Zbl 1005.05034
Summary: We prove a decomposition theorem for even-hole-free graphs. The decompositions used are 2-joins and star, double-star and triple-star cutsets. This theorem is used in the second part of this paper to obtain a polytime recognition algorithm for even-hole-free graphs.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C17 Perfect graphs
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bienstock, On complexity of testing for odd holes and induced odd paths, Discrete Math 90 pp 85– (1991) · Zbl 0753.05046
[2] Burlet, Polynomial algorithm to recognize a Meyniel graph, Ann of Discrete Math 21 pp 225– (1984) · Zbl 0552.05058
[3] Chvátal, Star cutsets and perfect graphs, J Combin Theory B 39 pp 189– (1985) · Zbl 0674.05058
[4] Conforti, Balanced 0,{\(\pm\)}1 matrices, Parts I and II, J Combin Theory B 81 pp 243– (2001) · Zbl 1026.05016
[5] Conforti, Even-hole-free graphs, Part II: Recognition algorithm, J Graph Theory (1997)
[6] Conforti, Even and odd holes in cap-free graphs, J Graph Theory 30 pp 289– (1999) · Zbl 0920.05028
[7] Conforti, Triangle-free graphs that are signable without even holes, J Graph Theory 34 pp 204– (2000) · Zbl 0953.05061
[8] Conforti, Decomposition of balanced matrices, J Combin Theory B 77 pp 292– (1999) · Zbl 1023.05025
[9] Conforti, A theorem of Truemper, Combin 20 pp 15– (2000) · Zbl 0949.05071
[10] Cornuéjols, Composition for perfect graphs, Discrete Math 55 pp 245– (1985) · Zbl 0562.05043
[11] J. F. Geelen Matchings, Matroids and Unimodular Matrices 1995
[12] Markossian, {\(\beta\)}-Perfect graphs, J Combin Theory B 67 pp 1– (1996) · Zbl 0857.05038
[13] O. Porto Even induced cycles in planar graphs 1992
[14] Truemper, Alpha-balanced graphs and matrices and GF(3)-representability of matroids, J Combin Theory B 32 pp 112– (1982) · Zbl 0478.05026
[15] West, Introduction to Graph Theory (1996) · Zbl 0845.05001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.