𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A randomized algorithm for k-colorability

✍ Scribed by Janez Žerovnik

Book ID
103061079
Publisher
Elsevier Science
Year
1994
Tongue
English
Weight
692 KB
Volume
131
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

This note is a report of testing a straightforward generalization of the randomized 3-coloring algorithm of Petford and Welsh (1989) on the decision problems of 4-and lo-coloring.

We observe similar behavior, namely the existence of critical regions. Experimentally, the average time complexity for large n again seems to grow slowly, although in some cases the number of transitions needed is prohibitively high for practical applications.

📜 SIMILAR VOLUMES

A Sharp Threshold for k-Colorability
A Sharp Threshold for k-Colorability
✍ Dimitris Achlioptas; Ehud Friedgut 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB

Let k be a fixed integer and f n, p denote the probability that the random k Ž . Ž . graph G n, p is k-colorable. We show that for k G 3, there exists d n such that for any k ⑀ ) 0, d n y ⑀ d n q ⑀ Ž . Ž .

Algorithms for coloring semi-random grap
Algorithms for coloring semi-random graphs
✍ C. R. Subramanian; Martin Fürer; C. E. Veni Madhavan 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 373 KB 👁 3 views

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require ␦ Ž . Ž . n ␦ ) 0 colors even for bounded chromatic k-co

A Better Algorithm for Random k -SAT
A Better Algorithm for Random k -SAT
✍ Coja-Oghlan, Amin 📂 Article 📅 2010 🏛 Society for Industrial and Applied Mathematics 🌐 English ⚖ 499 KB
Algorithms for maximum k-colorings and k
Algorithms for maximum k-colorings and k-coverings of transitive graphs
✍ Fǎnicǎ Gavril 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 356 KB

Consider a graph G and a positive integer k. The maximum k-coloring problem is to color a maximum number of vertices using k colors, such that no two adjacent vertices have the same color. The maximum k-covering problem is to find k disjoint cliques covering a maximum number of vertices. The present

A fast algorithm for equitable coloring
A fast algorithm for equitable coloring
✍ Henry A. Kierstead; Alexandr V. Kostochka; Marcelo Mydlarz; Endre Szemerédi 📂 Article 📅 2010 🏛 Springer-Verlag 🌐 English ⚖ 399 KB