Detecting even holes

DOI10.1002/jgt.20040zbMath1062.05135OpenAlexW4248219865MaRDI QIDQ4667791

Maria Chudnovsky, Ken-ichi Kawarabayashi, P. D. Seymour

Publication date: 21 April 2005

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.20040

zbMATH Keywords

signed graphrecognition algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items

Detecting a long even hole, Finding a shortest even hole in polynomial time, The Induced Disjoint Paths Problem, Finding induced paths of given parity in claw-free graphs, The \(k\)-in-a-path problem for claw-free graphs, On the structure of (pan, even hole)‐free graphs, On the forbidden induced subgraph sandwich problem, Algorithms for finding an induced cycle in planar graphs, Bisimplicial vertices in even-hole-free graphs, On the structure of (even hole, kite)-free graphs, On the complexity of finding chordless paths in bipartite graphs and some interval operators in graphs and hypergraphs, Some completion problems for graphs without chordless cycles of prescribed lengths, The parameterized complexity of \(k\)-edge induced subgraphs, Induced packing of odd cycles in planar graphs, Unnamed Item, A faster algorithm to recognize even-hole-free graphs