Detecting even holes

DOI10.1002/JGT.20040MaRDI QIDQ4667791zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Ken-ichi Kawarabayashi, Paul 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)

Recommendations

• A faster algorithm to recognize even-hole-free graphs
• A faster algorithm to recognize even-hole-free graphs
• Even-hole-free graphs part II: Recognition algorithm
• Even and odd holes in cap-free graphs
• Finding a shortest even hole in polynomial time

Cited in

(21)

• Finding a shortest even hole in polynomial time
• 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
• Hole and antihole detection in graphs
• The Induced Disjoint Paths Problem
• Detecting holes and antiholes in graphs
• The parameterized complexity of k-edge induced subgraphs
• Detecting a long even hole
• Shortest odd paths in undirected graphs with conservative weight functions
• A faster algorithm to recognize even-hole-free graphs
• Induced packing of odd cycles in planar graphs
• Some completion problems for graphs without chordless cycles of prescribed lengths
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• On the forbidden induced subgraph sandwich problem
• Algorithms for finding an induced cycle in planar graphs
• The \(k\)-in-a-path problem for claw-free graphs
• On the structure of (pan, even hole)-free graphs
• A faster algorithm to recognize even-hole-free graphs
• Detecting an Odd Hole
• Bisimplicial vertices in even-hole-free graphs
• Finding induced paths of given parity in claw-free graphs

This page was built for publication: Detecting even holes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4667791)