Expose-and-merge exploration and the chromatic number of a random graph

DOI10.1007/BF02579304zbMath0648.05049MaRDI QIDQ1104942

David W. Matula

Publication date: 1987

Published in: Combinatorica (Search for Journal in Brave)

zbMATH Keywords

algorithmrandom graphschromatic number

Mathematics Subject Classification ID

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

Related Items (16)

Solving the maximum clique problem using a tabu search approach ⋮ Coloring random graphs ⋮ Undecidable statements and random graphs ⋮ Upper-bounding the \(k\)-colorability threshold by counting covers ⋮ Lower bounds on the chromatic number of random graphs ⋮ On the chromatic number of random regular graphs ⋮ The Triangle-Free Process and the Ramsey Number 𝑅(3,𝑘) ⋮ Planting Colourings Silently ⋮ On the independence number of random graphs ⋮ The chromatic number of random graphs ⋮ The chromatic number of random graphs ⋮ Equitable coloring of random graphs ⋮ Local convergence of random graph colorings ⋮ On the Number of Solutions in Random Graphk-Colouring ⋮ Improved Bounds on Induced Acyclic Subgraphs in Random Digraphs ⋮ A note on the chromatic number of a dense random graph

Cites Work

• Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
• On colouring random graphs
• Cliques in random graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Expose-and-merge exploration and the chromatic number of a random graph