Structures and chromaticity of extremal 3-colourable sparse graphs

DOI10.1007/PL00007254MaRDI QIDQ5956100zbMATH OpenOpenAlexFDO

Authors F. M. Dong, K. M. Koh, K. L. Teo

Publication date 14 July 2002

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/pl00007254

zbMATH Keywords

2-treeschordal graphschromatic polynomialchromatically unique graphsuniquely colourable graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35)

Review text

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.

Recommendations

• Structures and chromaticity of some extremal 3-colourable graphs
• The chromaticity of certain graphs with five triangles
• A note on graph colouring
• On the chromatic uniqueness of the graph \(W(n,n-2,k)\)
• scientific article; zbMATH DE number 742643

Cited in

(5)

• Structures and chromaticity of some extremal 3-colourable graphs
• On graphs in which any pair of colour classes but one induces a tree
• 3-colouring for dually chordal graphs and generalisations
• Extremal properties of the chromatic polynomials of connected 3-chromatic graphs
• On the density of 2-colorable 3-graphs in which any four points span at most two edges

This page was built for publication: Structures and chromaticity of extremal 3-colourable sparse graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956100)