Structures and Chromaticity of Extremal 3-Colourable Sparse Graphs |
| |
Authors: | FM Dong KM Koh KL Teo |
| |
Institution: | (1) Institute of Fundamental Sciences (Mathematics), Massey University, Palmerston North, New Zealand. e-mail: fmdong@nie.edu.sg, NZ;(2) Department of Mathematics, National University of Singapore, Singapore, SG |
| |
Abstract: | Assume that G is a 3-colourable connected graph with e(G) = 2v(G) −k, where k≥ 4. It has been shown that s
3(G) ≥ 2
k
−3, where s
r
(G) = P(G,r)/r! for any positive integer r and P(G, λ) is the chromatic polynomial of G. In this paper, we prove that if G is 2-connected and s
3(G) < 2
k
−2, then G contains at most v(G) −k triangles; and the upper bound is attained only if G is a graph obtained by replacing each edge in the k-cycle C
k
by a 2-tree. By using this result, we settle the problem of determining if W(n, s) is χ-unique, where W(n, s) is the graph obtained from the wheel W
n
by deleting all but s consecutive spokes.
Received: January 29, 1999 Final version received: April 8, 2000 |
| |
Keywords: | , ,Chordal graphs, 2-Trees, Uniquely colourable graphs, Chromatic polynomial, Chromatically unique graphs |
本文献已被 SpringerLink 等数据库收录! |
|