A bound on the treewidth of planar even-hole-free graphs

DOI10.1016/J.DAM.2009.07.010MaRDI QIDQ987668zbMATHOpenAlexFDO

Authors J. Martínez

Publication date 13 August 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.07.010

zbMATH Keywords

bounded treewidthplanar graphseven-hole-free graphsforbidden minor

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

Recommendations

• Even-hole-free planar graphs have bounded treewidth
• On the tree-width of even-hole-free graphs
• Quickly excluding a planar graph
• scientific article; zbMATH DE number 1262812
• Tree-width and large grid minors in planar graphs

Cites work

• On planar geodetic graphs
• Quickly excluding a planar graph
• The four-colour theorem

Cited in

(9)

• (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
• On the tree-width of even-hole-free graphs
• Even-hole-free planar graphs have bounded treewidth
• Finding a shortest even hole in polynomial time
• Structure and algorithms for (cap, even hole)-free graphs
• Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree
• A faster algorithm to recognize even-hole-free graphs
• A class of graphs with large rankwidth
• Treewidth versus clique number. I: Graph classes with a forbidden structure

This page was built for publication: A bound on the treewidth of planar even-hole-free graphs

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