A local strengthening of Reed's ω, Δ, χ conjecture for quasi-line graphs

Details A local strengthening of Reed's ω, Δ, χ conjecture for quasi-line graphs A local strengthening of Reed's ω, Δ, χ conjecture for quasi-line graphs

2011-09-09

arxiv.org/abs/1109.2112v2

Computer Science

Discrete Mathematics

18 pages, 1 figure

Scientific paper

Reed's $\omega$, $\Delta$, $\chi$ conjecture proposes that every graph satisfies $\chi\leq \lceil\frac 12(\Delta+1+\omega)\rceil$; 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 colourings that achieve our bounds: $O(n^2)$ for line graphs and $O(n^3m^2)$ for quasi-line graphs. For line graphs, this is faster than the best known algorithm for constructing a colouring that achieves the bound of Reed's original conjecture.

Affiliated with

Also associated with

No associations

Rating

A local strengthening of Reed's ω, Δ, χ conjecture for quasi-line graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A local strengthening of Reed's ω, Δ, χ conjecture for quasi-line graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A local strengthening of Reed's ω, Δ, χ conjecture for quasi-line graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-414408