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

DOI10.1016/J.DAM.2009.07.010zbMATH Open1231.05080OpenAlexW2096563151MaRDI QIDQ987668FDOQ987668

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

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

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)

Cites Work

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

Cited In (9)

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

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)