Random I‐colorable graphs

DOI10.1002/rsa.3240060104zbMath0817.05052OpenAlexW2130763052MaRDI QIDQ4322472

Angelika Steger, Hans Jürgen Prömel

Publication date: 9 February 1995

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.3240060104

zbMATH Keywords

chromatic numberrandom graphcoloringthreshold function

Mathematics Subject Classification ID

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

Related Items (5)

Why almost all \(k\)-colorable graphs are easy to color ⋮ The typical structure of sparse $K_{r+1}$-free graphs ⋮ Representation of graphs by OBDDs ⋮ An efficient container lemma ⋮ Asymptotic probabilities of extension properties and random \(l\)-colourable structures

Cites Work

• Graphs with small chromatic numbers are easy to color
• A note on the sharp concentration of the chromatic number of random graphs
• The Number of k-Coloured Graphs on Labelled Nodes
• Almost all k-colorable graphs are easy to color
• Counting Coloured Graphs of High Connectivity
• The chromatic number of random graphs

This page was built for publication: Random I‐colorable graphs