Algorithms for Colouring Random k-colourable Graphs

DOI10.1017/S0963548399004137MaRDI QIDQ4948046zbMATH OpenFDO

Authors C. R. Subramanian

Publication date 8 November 2000

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1017/S0963548399004137

zbMATH Keywords

colour classescolouring algorithmsrandom \(k\)-colourable graphs

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1962838
• Mathematical Foundations of Computer Science 2005
• Coloring random graphs
• Why almost all k-colorable graphs are easy to color
• Minimum Coloring k-Colorable Graphs in Polynomial Average Time

Cited in

(23)

• A randomised heuristical algorithm for estimating the chromatic number of a graph
• A randomized algorithm for \(k\)-colorability
• scientific article; zbMATH DE number 1670678 (Why is no real title available?)
• Short Note: A Las Vegas graph Colouring Algorithm
• scientific article; zbMATH DE number 434500 (Why is no real title available?)
• scientific article; zbMATH DE number 4210190 (Why is no real title available?)
• scientific article; zbMATH DE number 5004842 (Why is no real title available?)
• Randomly colorable graphs in greedy coloring
• Why Almost All k-Colorable Graphs Are Easy
• A Random Recolouring Method for Graphs and Hypergraphs
• A Spectral Technique for Coloring Random 3-Colorable Graphs
• scientific article; zbMATH DE number 1984543 (Why is no real title available?)
• Minimum Coloring k-Colorable Graphs in Polynomial Average Time
• scientific article; zbMATH DE number 7368393 (Why is no real title available?)
• Coloring random graphs
• Algorithms for the Rainbow Vertex Coloring Problem on Graph Classes
• Mathematical Foundations of Computer Science 2005
• scientific article; zbMATH DE number 956851 (Why is no real title available?)
• A simple algorithm for random colouring G(n, d/n) using (2 + )d colours
• Coloring k-colorable graphs in constant expected parallel time
• Coloring in sublinear time
• Random sampling of colourings of sparse random graphs with a constant number of colours
• Why almost all k-colorable graphs are easy to color

This page was built for publication: Algorithms for Colouring Random k-colourable Graphs

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