Coloring quasi‐line graphs |
| |
| Authors: | Maria Chudnovsky Alexandra Ovetsky |
| |
| Institution: | 1. Department of Mathematics, Princeton University Princeton, NJ 08544;2. This research was conducted while the author served as a Clay Mathematics Institute Research Fellow. |
| |
| Abstract: | A graph G is a quasi‐line graph if for every vertex v, the set of neighbors of v can be expressed as the union of two cliques. The class of quasi‐line graphs is a proper superset of the class of line graphs. A theorem of Shannon's implies that if G is a line graph, then it can be properly colored using no more than 3/2 ω(G) colors, where ω(G) is the size of the largest clique in G. In this article, we extend this result to all quasi‐line graphs. We also show that this bound is tight. © 2006 Wiley Periodicals, Inc. J Graph Theory |
| |
| Keywords: | claw‐free graphs quasi‐line graphs coloring |
|
|
