A FRACTIONAL ANALOGUE OF BROOKS%26apos; THEOREM

作者：King Andrew D^*; Lu Linyuan; Peng Xing

来源：SIAM Journal on Discrete Mathematics, 2012, 26(2): 452-471.

DOI：10.1137/110827879

• fractional chromatic number
• Brooks%26apos
• theorem
• chromatic number

Let Delta(G) be the maximum degree of a graph G. Brooks%26apos; theorem states that the only connected graphs with chromatic number chi(G) = Delta(G) + 1 are complete graphs and odd cycles. We prove a fractional analogue of Brooks%26apos; theorem in this paper. Namely, we classify all connected graphs G such that the fractional chromatic number chi(f) (G) is at least Delta(G). These graphs are complete graphs, odd cycles, C-8(2), C-5 boxed times K-2, and graphs whose clique number omega(G) equals the maximum degree Delta(G). Among the two sporadic graphs, the graph C-8(2) is the square graph of cycle C-8, while the other graph C-5 boxed times K-2 is the strong product of C-5 and K-2. In fact, we prove a stronger result: If a connected graph G with Delta(G) %26gt;= 4 is not one of the graphs listed above, then we have chi(f)(G) %26lt;= Delta(G) - 2/67.

• 出版日期2012