Brooks' graph-coloring theorem and the independence number |
| |
Authors: | Paul A Catlin |
| |
Affiliation: | Depatment of Mathematics, Wayne State University, Detroit, Michigan 48202 USA |
| |
Abstract: | Let h denote the maximum degree of a connected graph H, and let χ(H) denote its chromatic, number. Brooks' Theorem asserts that if h ≥ 3, then χ(H) ≤ h, unless H is the complete graph Kh+1. We show that when H is not Kh+1, there is an h-coloring of H in which a maximum independent set is monochromatic. We characterize those graphs H having an h-coloring in which some color class consists of vertices of degree h in H. Again, without any loss of generality, this color class may be assumed to be maximum with respect to the condition that its vertices have degree h. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|