2011/01/29 by Mohammad Shoaib Jamall, Jamall, Mohammad Shoaib
Computer Science · Mathematics · #05C15 (Primary) 05C85 #68Q87 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1101.5721
openalex publication_date 2011/01/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a randomized algorithm that properly colors the vertices of a triangle-free graph G on n vertices using O(Δ(G)/ log Δ(G)) colors, where Δ(G) is the maximum degree of G. The algorithm takes O(nΔ2(G)logΔ(G)) time and succeeds with high probability, provided Δ(G) is greater than log1+εn for a positive constant ε. 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.