A bound on the treewidth of planar even-hole-free graphs |
| |
| Authors: | Ana Silva Aline Alves da Silva |
| |
| Institution: | a Laboratoire G-SCOP, Université Joseph Fourier (Grenoble I), 46 av. Félix Viallet 38000 Grenoble, France
b Departamento de Computação - UFC, Campus do Pici, bloco 910, CEP 60455-760, Fortaleza, Brazil |
| |
| Abstract: | The class of planar graphs has unbounded treewidth, since the k×k grid, ∀k∈N, is planar and has treewidth k. So, it is of interest to determine subclasses of planar graphs which have bounded treewidth. In this paper, we show that if G is an even-hole-free planar graph, then it does not contain a 9×9 grid minor. As a result, we have that even-hole-free planar graphs have treewidth at most 49. |
| |
| Keywords: | Planar graphs Even-hole-free graphs Bounded treewidth Forbidden minor |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
