Search

In 1998 the second author proved that there is an ε > 0 such that every graph satisfies ≤ [(1 - ε)(Δ+ 1) + εω]. The first author recently proved that any graph satisfying ω > 23 (Δ + 1) contains a stable set intersecting every maximum clique. In this note, we exploit the latter result to give a much shorter, simpler proof of the former. Working from first principles, we omit only some five pages of proofs of known intermediate results (which appear in an extended version of this paper), and the proofs of Hall's Theorem, Brooks' Theorem, the Lovász Local Lemma, and Talagrand's Inequality. [ABSTRACT FROM AUTHOR]

The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies [ABSTRACT FROM AUTHOR]

As proved by Kahn, the chromatic number and fractional chromatic number of a line graph agree asymptotically.That is, for any line graph G, we have [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]