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-coloringrandomised algorithmthreshold function

Mathematics Subject Classification ID

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

Review text

Trying to extend the voter and antivoter model used to 2-color a graph, the authors introduce a randomised algorithm to 3-color a graph. Simulation results are reported.

Cites work

• Finite particle systems and infection models
• Graph theory
• 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?)
• Optimization by simulated annealing
• Randomised algorithms
• Some simplified NP-complete graph problems
• The complexity of colouring problems on dense graphs

Cited in

(16)

• \(L(2,1)\)-labeling of strong products of cycles
• A randomized algorithm for \(k\)-colorability
• \(L(2,1)\)-labeling of direct product of paths and cycles
• Improved lower bound on the Shannon capacity of C₇
• Clustering as a dual problem to colouring
• 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
• A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs
• Clustering via the modified Petford-Welsh algorithm
• Chromatic numbers of the strong product of odd cycles
• A Random Recolouring Method for Graphs and Hypergraphs
• scientific article; zbMATH DE number 2230321 (Why is no real title available?)
• Models and solution techniques for frequency assignment problems
• k-phase oscillator synchronization for graph coloring
• A fresh look at a randomized massively parallel graph coloring algorithm
• Dominic Welsh: his work and influence

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)