A randomised 3-colouring algorithm

DOI10.1016/0012-365X(89)90214-8MaRDI QIDQ1117242zbMATH OpenOpenAlexFDO

Authors A. D. Petford, D. J. A. Welsh

Publication date 1989

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(89)90214-8

zbMATH Keywords

3-coloringthreshold functionrandomised algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Algorithms in computer science (68W99)

Cites work

• scientific article; zbMATH DE number 4013719 (Why is no real title available?)
• scientific article; zbMATH DE number 3928066 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Finite particle systems and infection models
• Graph theory
• Optimization by simulated annealing
• Randomised algorithms
• Some simplified NP-complete graph problems
• The complexity of colouring problems on dense graphs

Cited in

(15)

• A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs
• A Random Recolouring Method for Graphs and Hypergraphs
• Reachability and recurrence in a modular generalization of annihilating random walks (and Lights-Out games) to hypergraphs
• Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm
• Improved lower bound on the Shannon capacity of C₇
• scientific article; zbMATH DE number 2230321 (Why is no real title available?)
• A fresh look at a randomized massively parallel graph coloring algorithm
• \(L(2,1)\)-labeling of direct product of paths and cycles
• \(L(2,1)\)-labeling of strong products of cycles
• Clustering via the modified Petford-Welsh algorithm
• k-phase oscillator synchronization for graph coloring
• Models and solution techniques for frequency assignment problems
• A randomized algorithm for \(k\)-colorability
• Chromatic numbers of the strong product of odd cycles
• Clustering as a dual problem to colouring

This page was built for publication: A randomised 3-colouring algorithm

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