A Coloring Algorithm for Triangle-Free Graphs

Details A Coloring Algorithm for Triangle-Free Graphs A Coloring Algorithm for Triangle-Free Graphs

2011-01-29

arxiv.org/abs/1101.5721v1

Mathematics

Combinatorics

22 pages

Scientific paper

We give a randomized algorithm that properly colors the vertices of a triangle-free graph G on n vertices using O(\Delta(G)/ log \Delta(G)) colors, where \Delta(G) is the maximum degree of G. The algorithm takes O(n\Delta2(G)log\Delta(G)) time and succeeds with high probability, provided \Delta(G) is greater than log^{1+{\epsilon}}n for a positive constant {\epsilon}. The number of colors is best possible up to a constant factor for triangle-free graphs. As a result this gives an algorithmic proof for a sharp upper bound of the chromatic number of a triangle-free graph, the existence of which was previously established by Kim and Johansson respectively.

Affiliated with

Also associated with

No associations

Rating

A Coloring Algorithm for Triangle-Free Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Coloring Algorithm for Triangle-Free Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Coloring Algorithm for Triangle-Free Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-157582