Search

King, Lu, and Peng recently proved that for Δ ≥ 4, any KΔ-free graph with maximum degree Δ has fractional chromatic number at most Δ - 2/67 unless it is isomorphic to C5 ... K2 or C8². Using a different approach we give improved bounds for Δ ≥ 6 and pose several related conjectures. Our proof relies on a weighted local generalization of the fractional relaxation of Reed's ω, Δ, χ conjecture. [ABSTRACT FROM AUTHOR]

Reed's w, Δ, χ conjecture proposes that every graph satisfies χ ≤ [1/2(Δ + 1 + w)] it is known to hold for all claw-free graphs. In this paper we consider a local strengthening of this conjecture. We prove the local strengthening for line graphs, then note that previous results immediately tell us that the local strengthening holds for all quasi-line graphs. Our proofs lead to polytime algorithms for constructing colorings that achieve our bounds: O(n²) for line graphs and O(n³m²) for quasi-line graphs. For line graphs, this is faster than the best known algorithm for constructing a coloring that achieves the bound of Reed's original conjecture. [ABSTRACT FROM AUTHOR]

Let Δ (G) be the maximum degree of a graph G. Brooks' theorem states that the only connected graphs with chromatic number X(G) = Δ (G) + 1 are complete graphs and odd cycles. We prove a fractional analogue of Brooks' theorem in this paper. Namely, we classify all connected graphs G such that the fractional chromatic number Xf(G) is at least Δ (G). These graphs are complete graphs, odd cycles, C²8 C5 ⊠ K2, and graphs whose clique number ω(G) equals the maximum degree Δ (G). Among the two sporadic graphs, the graph C²8 is the square graph of cycle C8, while the other graph C5 ⊠ K2 is the strong product of C5 and K2. In fact, we prove a stronger result: If a connected graph G with δ (G) ≥ 4 is not one of the graphs listed above, then we have Xf(G)≤ Δ(G) -- 2/67. [ABSTRACT FROM AUTHOR]