Please use this identifier to cite or link to this item:
Title: Structures and chromaticity of extremal 3-colourable sparse graphs
Authors: Dong, F.M.
Koh, K.M. 
Teo, K.L.
Keywords: 2-Trees
Chordal graphs
Chromatic polynomial
Chromatically unique graphs
Uniquely colourable graphs
Issue Date: 2001
Source: Dong, F.M.,Koh, K.M.,Teo, K.L. (2001). Structures and chromaticity of extremal 3-colourable sparse graphs. Graphs and Combinatorics 17 (4) : 611-635. ScholarBank@NUS Repository.
Abstract: Assume that G is a 3-colourable connected graph with e(G) = 2v(G) - k, where k ≥ 4. It has been shown that s3(G) ≥ 2k-3, where sr(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 s3(G) < 2k-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 Ck 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 Wn by deleting all but s consecutive spokes. © Springer-Verlag 2001.
Source Title: Graphs and Combinatorics
ISSN: 09110119
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

checked on Jan 19, 2018

Google ScholarTM


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.