𝔖 Bobbio Scriptorium
✦   LIBER   ✦

An Õ(n314)-coloring algorithm for 3-colorable graphs

✍ Scribed by Avrim Blum; David Karger

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
471 KB
Volume
61
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

✦ Synopsis

We show how the results of Karger, Motwani, and Sudan ( 1994) and Blum ( 1994) can be combined in a natural manner to yield a polynomial-time algorithm for d(n3"4 )-coloring any n-node 3-colorable graph. This improves on the previous best bound of 6(n'14) colors (Karger et al., 1994).

📜 SIMILAR VOLUMES

An O(n) time algorithm for maximum match
An O(n) time algorithm for maximum matching in P4-tidy graphs
✍ J.L. Fouquet; I. Parfenoff; H. Thuillier 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 630 KB

The A-tidy graphs were introduced by I. Rusu to generalize some already known classes of graphs with "few" induced P4 s. In this paper, we extend to PA-tidy graphs a linear time algorithm of C.-H. Yang and M.-S. Yu for finding a maximum matching in a cograph G (given a parse tree associated to G). @