scientific article; zbMATH DE number 3985277

MaRDI QIDQ3749092zbMATH OpenFDO

Authors W. Fernandez de la Vega

Publication date 1985

zbMATH Keywords

colouring algorithmlargest stable setrandom graph

Mathematics Subject Classification ID

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

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

Cited in

(12)

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

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)