Structures and chromaticity of extremal 3-colourable sparse graphs (Q5956100)
From MaRDI portal
scientific article; zbMATH DE number 1708493
Language | Label | Description | Also known as |
---|---|---|---|
English | Structures and chromaticity of extremal 3-colourable sparse graphs |
scientific article; zbMATH DE number 1708493 |
Statements
Structures and chromaticity of extremal 3-colourable sparse graphs (English)
0 references
14 July 2002
0 references
Let \(G\) be a \(3\)-colourable graph with \(n\) vertices and \(2n-k\) edges. Let \(s_r(G)=P(G,r)r!\) where \(P(G,\lambda)\) is the chromatic polynomial of \(G\). The authors show that \(s_3(G)\geq 2^{k-3}\). Moreover, if \(G\) is \(2\)-connected and \(s_3(G) < 2^{k-2}\), then \(G\) contains at most \(n-k\) triangles. They also describe the structure of graphs attaining the upper bound. By using this result they prove that the graphs \(W(n,s)\) obtained from the \(n\)-wheel by deleting all but \(s\) consecutive spokes are, in most cases, chromatically unique.
0 references
chromatic polynomial
0 references
chromatically unique graphs
0 references
uniquely colourable graphs
0 references
2-trees
0 references
chordal graphs
0 references