Coloring random graphs

DOI10.1016/S0020-0190(98)00092-1MaRDI QIDQ293318zbMATHOpenAlexFDO

Authors Michael Krivelevich, Benny Sudakov

Publication date 9 June 2016

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL http://www.sciencedirect.com/science/article/pii/S0020019098000921?np=y

zbMATH Keywords

analysis of algorithmsrandom graphs: graph coloring

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Coloring random graphs
• Coloring random graphs
• Randomly coloring random graphs
• Colouring random graphs
• scientific article; zbMATH DE number 4101221
• scientific article; zbMATH DE number 4134071
• Colouring Random Regular Graphs
• scientific article; zbMATH DE number 1984543
• Randomly colouring graphs (a combinatorial view)
• Randomly colorable graphs in greedy coloring

Cites work

• scientific article; zbMATH DE number 986986 (Why is no real title available?)
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 4101221 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 3574966 (Why is no real title available?)
• Cliques in random graphs
• Expose-and-merge exploration and the chromatic number of a random graph
• Large Cliques Elude the Metropolis Process
• On colouring random graphs
• The chromatic number of random graphs

Cited in

(15)

• Colouring Random Regular Graphs
• Painting a graph with competing random walks
• Randomly coloring random graphs
• Superlogarithmic cliques in dense inhomogeneous random graphs
• Randomly colouring graphs (a combinatorial view)
• Coloring Random Intersection Graphs and Complex Networks
• Improved bounds on induced acyclic subgraphs in random digraphs
• Induced acyclic tournaments in random digraphs: sharp concentration, thresholds and algorithms
• Planting colourings silently
• Local convergence of random graph colorings
• scientific article; zbMATH DE number 1962838 (Why is no real title available?)
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces
• Coloring random graphs
• scientific article; zbMATH DE number 881158 (Why is no real title available?)
• Colouring Random 4-Regular Graphs

This page was built for publication: Coloring random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q293318)