Article ID Journal Published Year Pages File Type
4656991 Journal of Combinatorial Theory, Series B 2011 20 Pages PDF
Abstract

Reed conjectured that for every ϵ>0 and Δ there exists g such that the fractional total chromatic number of a graph with maximum degree Δ and girth at least g is at most Δ+1+ϵ. We prove the conjecture for Δ=3 and for even Δ⩾4 in the following stronger form: For each of these values of Δ, there exists g such that the fractional total chromatic number of any graph with maximum degree Δ and girth at least g is equal to Δ+1.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics