scientific article; zbMATH DE number 3985277

zbMATH Open0609.05060MaRDI QIDQ3749092FDOQ3749092

Authors: W. Fernandez de la Vega 

Publication date: 1985

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 1962838
• The chromatic number of random graphs
• On the chromatic number of random graphs
• Exact and approximative algorithms for coloring G(n,p)
• On the chromatic number of random graphs

zbMATH Keywords

random graphcolouring algorithmlargest stable set

Mathematics Subject Classification ID

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

Cited In (12)

• Average-case complexity of backtrack search for coloring sparse random graphs
• How to make a random graph irregular
• Kolmogorov random graphs only have trivial stable colorings.
• Random reals and polarized colorings
• Graphs with small chromatic numbers are easy to color
• The greedy coloring is a bad probabilistic algorithm
• Sparse graphs usually have exponentially many optimal colorings
• On the order of the largest induced tree in a random graph
• The chromatic number of random graphs
• Solving NP-hard semirandom graph problems in polynomial expected time
• Matching and covering the vertices of a random graph by copies of a given graph
• Title not available (Why is that?)

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