Triangle-free graphs that are signable without even holes
Michele Conforti, G�rard Cornu�jols, Ajai Kapoor, Kristina Vu?kovi? · Journal of Graph Theory · 2000
We characterize triangle-free graphs for which there exists a subset of edges that intersects every chordless cycle in an odd number of edges (TF odd-signable graphs). These graphs arise as building blocks of a decomposition theorem (for cap-free odd-signable graphs) obtained by the same authors. We give a polytime algorithm to test membership in this class. This algorithm is itself based on a decomposition theorem. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 204–220, 2000