scientific article; zbMATH DE number 4213473

MaRDI QIDQ3359787zbMATH OpenFDO

Authors Luděk Kučera, David W. Matula

Publication date 1990

zbMATH Keywords

randomized algorithm

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Expose-and-merge exploration and the chromatic number of a random graph
• Coloring random graphs
• An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
• scientific article; zbMATH DE number 1962838
• The chromatic number of random intersection graphs

Cited in

(9)

• Expose-and-merge exploration and the chromatic number of a random graph
• Expected complexity of graph partitioning problems
• The stable set problem: clique and nodal inequalities revisited
• Lower bounds on the chromatic number of random graphs
• The t-improper chromatic number of random graphs
• Separation choosability and dense bipartite induced subgraphs
• On the chromatic number of random graphs
• Coloring k-colorable graphs in constant expected parallel time
• Dominating K_t-models

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 Q3359787)