A randomised 3-colouring algorithm

DOI10.1016/0012-365X(89)90214-8zbMath0667.05025OpenAlexW2068179205MaRDI QIDQ1117242

A. D. Petford, Dominic 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)

Related Items (14)

A randomized algorithm for \(k\)-colorability ⋮ Clustering as a dual problem to colouring ⋮ Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm ⋮ A Random Recolouring Method for Graphs and Hypergraphs ⋮ \(k\)-phase oscillator synchronization for graph coloring ⋮ Clustering via the modified Petford-Welsh algorithm ⋮ Unnamed Item ⋮ \(L(2,1)\)-labeling of direct product of paths and cycles ⋮ Models and solution techniques for frequency assignment problems ⋮ Unnamed Item ⋮ \(L(2,1)\)-labeling of strong products of cycles ⋮ Improved lower bound on the Shannon capacity of \(C_7\) ⋮ A novel giant-subgraph phase-transition in sparse random \(k\)-partite graphs ⋮ Reachability and recurrence in a modular generalization of annihilating random walks (and Lights-Out games) to hypergraphs

Cites Work

• Optimization by Simulated Annealing
• The complexity of colouring problems on dense graphs
• Some simplified NP-complete graph problems
• Randomised algorithms
• Finite particle systems and infection models
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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