Structures and chromaticity of extremal 3-colourable sparse graphs (Q5956100)

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.