(Even hole, triangle)-free graphs revisited
This work addresses structural graph theory problems for researchers in discrete mathematics and computer science, offering incremental improvements in understanding and algorithmic bounds for specific graph classes.
The paper revisits a class of graphs previously studied as triangle-free odd signable graphs, generalizing it to (theta, triangle, wac)-free graphs and proving a stronger structure theorem with precise descriptions of basic classes and separators. Key results include a recognition algorithm with O(|V(G)|^4|E(G)|) running time, a proof that treewidth is at most 4 (improving a previous bound of 5), and a simple criterion for planarity.
We revisit a classical paper about (even hole, triangle)-free graphs [Conforti, Cornuéjols, Kapoor and Vu\v skoviÄ, Triangle-free graphs that are signable without even holes, Journal of Graph Theory, 34(3), 204--220, 2000]. In fact, the previous study describes a more general class, the so called triangle-free odd signable graphs, and we further generalise the class to the (theta, triangle, wac)-free graphs (not worth defining in an abstract). We exhibit a stronger structure theorem, by precisely describing basic classes and separators. We prove that the separators preserve the treewidth and several properties. Some consequences are a recognition algorithm with running time $O(|V(G)|^4|E(G)|)$, a proof that the treewidth of graphs in the class is at most~4 (improving a previous bound of~5), and a simple criterion to decide if a graph in the class is planar.