首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号