scientific article; zbMATH DE number 4047752
[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.
- Two conjectures on uniquely totally colorable graphs
- Extremal graphs in some coloring problems
- Extremal problems for colourings of uniform hypergraphs
- scientific article; zbMATH DE number 3924805
- scientific article; zbMATH DE number 568840
- Two extremal problems in graph theory
- Extremal Graph Problems for Graphs with a Color-Critical Vertex
- scientific article; zbMATH DE number 1047736
- An extremal problem on non-full colorable graphs
- scientific article; zbMATH DE number 3924817
- A bibliography on chromatic polynomials
- On small uniquely vertex-colourable graphs and Xu's conjecture
- On 1-uniqueness and dense critical graphs for tree-depth
- The size of uniquely colorable graphs
- scientific article; zbMATH DE number 1094148 (Why is no real title available?)
- Colourings of (k-r,k)-trees
- scientific article; zbMATH DE number 4183438 (Why is no real title available?)
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)