scientific article; zbMATH DE number 4047752

From MaRDI portal
Publication:3784094





[For the entire collection see Zbl 0634.00003.] We show that uniquely \((k+1)\)-colourable graphs of minimum size and with maximum number of triangles are precisely k-trees. It is a proof of two conjectures of \textit{M. Borowiecki}, \textit{H. P. Patil} [Graphs, Hypergraphs and Matroids, Proc. 5th Reg. Sci. Sess. Math., Zagań/Pol. 1985, 85 (1986)]. From this result we obtained a solution of \textit{Z. Skupień}'s problem [Graphs, Hypergraphs, Block designs; Sci, Pap. Inst. Math. Wrocław Tech. Univ. 17, Stud. Res. 13, 63-67 (1979; Zbl 0388.05017)]. Independently, \textit{C.-Y. Chao}, \textit{N.-Z. Li}, \textit{S.-J. Xu} [J. Graph Theory 10, 129-136 (1986; Zbl 0591.05021)] obtained similar results by different methods.











This page was built for publication:

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