Asymptotics of the chromatic number for quasi-line graphs

Details Asymptotics of the chromatic number for quasi-line graphs Asymptotics of the chromatic number for quasi-line graphs

2011-02-03

arxiv.org/abs/1102.0805v1

Computer Science

Discrete Mathematics

20 pages, 2 figures

Scientific paper

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 $\chi(G) \leq (1+o(1))\chi_f(G)$. We extend this result to quasi-line graphs, an important subclass of claw-free graphs. Furthermore we prove that we can construct a colouring that achieves this bound in polynomial time, giving us an asymptotic approximation algorithm for the chromatic number of quasi-line graphs.

Affiliated with

Also associated with

No associations

Rating

Asymptotics of the chromatic number 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 Asymptotics of the chromatic number for quasi-line graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Asymptotics of the chromatic number for quasi-line graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-491124