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

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