On total colourings of graphs

DOI10.1006/JCTB.1993.1010MaRDI QIDQ2277476zbMATH OpenOpenAlexFDO

Authors Colin McDiarmid, Bruce Reed

Publication date 1993

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/jctb.1993.1010

zbMATH Keywords

random graphtotal colouring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80)

Review text

We show that as \(n\to \infty\) the proportion of graphs on vertices 1,2,...,n with total chromatic number \(\chi >\Delta +1\) is very small; and the proportion with \(\chi >\Delta +2\) is very very small. Here \(\Delta\) denotes the maximum vertex degree. We also give an easy new deterministic upper bound on \(\chi \) (proved randomly).

Recommendations

• A bound on the total chromatic number
• Recent results on the total chromatic number
• scientific article; zbMATH DE number 798659
• A new upper bound for total colourings of graphs
• The total chromatic number of graphs having large maximum degree

Cited in

(33)

• Vertex-, edge-, and total-colorings of Sierpiński-like graphs
• On cocolourings and cochromatic numbers of graphs
• Fractionally colouring total graphs
• Recent developments in total colouring
• A new upper bound for total colourings of graphs
• Total-coloring of sparse graphs with maximum degree 6
• Total Thue colourings of graphs
• \((p,1)\)-total labelling of graphs
• Fractionally total colouring \(G_{n,p}\)
• On the total coloring of generalized Petersen graphs
• Total-colorings of complete multipartite graphs using amalgamations
• Total colorings of some multi-join graphs
• A characterization of graphs with fractional total chromatic number equal to \(\Delta +2\)
• scientific article; zbMATH DE number 4134071 (Why is no real title available?)
• scientific article; zbMATH DE number 4177084 (Why is no real title available?)
• scientific article; zbMATH DE number 5556311 (Why is no real title available?)
• Total Coloring With \Delta + \mbox\lowercasepoly(\log \Delta) Colors
• scientific article; zbMATH DE number 742644 (Why is no real title available?)
• scientific article; zbMATH DE number 1159270 (Why is no real title available?)
• Randomly colouring graphs (a combinatorial view)
• On word colourings and some perfect graphs
• An Improvement of Hind's Upper Bound on the Total Chromatic Number
• scientific article; zbMATH DE number 750697 (Why is no real title available?)
• A NOTE ON COLOURING OF COMPLETE GRAPHS
• scientific article; zbMATH DE number 810478 (Why is no real title available?)
• Total coloring of the prismatic graphs
• Total coloring of quasi-line graphs and inflated graphs
• scientific article; zbMATH DE number 6605085 (Why is no real title available?)
• Counting colorings of triangle-free graphs
• Recent results on the total chromatic number
• An upper bound for total colouring of graphs
• Some colouring problems for Paley graphs
• Total and fractional total colourings of circulant graphs

This page was built for publication: On total colourings of graphs

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