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.
Original language | English (US) |
---|---|
Pages (from-to) | 41-50 |
Number of pages | 10 |
Journal | Journal of Graph Theory |
Volume | 54 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2007 |
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Geometry and Topology
Keywords
- Claw-free graphs
- Coloring
- Quasi-line graphs