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

DOI10.1016/j.dam.2009.07.010zbMath1231.05080OpenAlexW2096563151MaRDI QIDQ987668

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

planar graphsforbidden minorbounded treewidtheven-hole-free graphs

Mathematics Subject Classification ID

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

Related Items (7)

Induced subgraphs and tree decompositions. I: Even-hole-free graphs of bounded degree ⋮ Structure and algorithms for (cap, even hole)-free graphs ⋮ Finding a shortest even hole in polynomial time ⋮ A class of graphs with large rankwidth ⋮ On the tree-width of even-hole-free graphs ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ A faster algorithm to recognize even-hole-free graphs

Cites Work

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

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