Please use this identifier to cite or link to this item:
|Title:||Structures and chromaticity of extremal 3-colourable sparse graphs|
Chromatically unique graphs
Uniquely colourable graphs
|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|
|Appears in Collections:||Staff Publications|
Show full item record
Files in This Item:
There are no files associated with this item.
checked on Jan 19, 2018
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.