| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4601807 | Linear Algebra and its Applications | 2011 | 7 Pages |
Abstract
Let μ(G) and ω(G) be the Colin de Verdière and clique numbers of a graph G, respectively. It is well-known that μ(G)⩾ω(G)-1 for all graphs. Our main results include μ(G)⩽ω(G) for all chordal graphs; μ(G)⩽tw(G)+1 for all graphs (where tw is the tree-width), and a characterization of those split (⊆ chordal) graphs for which μ(G)=ω(G). The bound μ(G)⩽tw(G)+1 improves a result of Colin de Verdière by a factor of 2.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
