Title of article
Tree width and regular triangulations
Author/Authors
Andrei Kotlov، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2001
Pages
5
From page
187
To page
191
Abstract
Consider the regular triangulation of an equilateral triangle into (k−1)2 congruent triangles. Define the graph Δk as the skeleton of this triangulation. Recently, using spectral methods, Colin de Verdière showed that the tree width of Δk is k. In this note, we show that Δk is, in fact, a forbidden minor for the property of having tree width less than k. As a corollary, we derive a similar result for a spectral graph invariant.
Keywords
Colin de Verdiere number , Forbidden minor , Tree width
Journal title
Discrete Mathematics
Serial Year
2001
Journal title
Discrete Mathematics
Record number
949761
Link To Document