Structures and chromaticity of some extremal 3-colourable graphs Original Research Article

Given a graph G and a positive integer r, let sr(G)=P(G,r)/r!. Thus χ(G)=r and sr(G)=1 iff G is uniquely r-colourable. It is known that if G is uniquely 3-colourable, then e(G)⩾2v(G)−3. In this paper, we show that if G is a 3-colourable connected graph with e(G)=2v(G)−k where k⩾4, then s3(G)⩾2k−3; and if, further, G is 2-connected and s3(G)=2k−3, then t(G)⩽v(G)−k where t(G) denotes the number of C3ʹs in G. We proceed to determine the structures of all 3-colourable 2-connected graphs G with e(G)=2v(G)−k, s3(G)=2k−3 and t(G)=v(G)−k. By applying this structural result, we finally study the chromaticity of such graphs and produce new chromatically equivalent classes.