Bounding χ in terms of ω and Δ for quasi-line graphs
✍ Scribed by Andrew D. King; Bruce A. Reed
- Publisher
- John Wiley and Sons
- Year
- 2008
- Tongue
- English
- Weight
- 156 KB
- Volume
- 59
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
A quasi‐line graph is a graph in which the neighborhood of any vertex can be covered by two cliques; every line graph is a quasi‐line graph. Reed conjectured that for any graph G, $\chi({{G}}) \leq\left \lceil {{{1}}\over {{2}}}(\Delta({{G}})+{{1}}+\omega({{G}}))\right\rceil$ [Reed, J Graph Theory 27 (1998), 177–212]. We prove that the conjecture holds if G is a quasi‐line graph, extending a result of King et al. who proved the conjecture for line graphs [Eur J Comb 28 (2007), 2182–2187], and improving the bound of $\chi{{(}}{{G}}{{)}} \leq {3\over 2} \omega({{G}})$ given by Chudnovsky and Ovetsky [J Graph Theory 54 (2007), 41–50]. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 215–228, 2008