Even‐hole‐free graphs part I: Decomposition theorem
Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, Kristina Vušković · Journal of Graph Theory · 2001
Abstract 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. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 6–49, 2002