Equitable -coloring of graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Bor-Liang Chen^a ; Chih-Hung Yen^b ; ^{chyen@mail.ncyu.edu.tw}
• 关键词：Equitable coloring ; Maximum degree ; Chromatic number ; Bipartite graphs ; Subcubic graphs
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：6 May, 2012
• 卷：312
• 期：9
• 页码：1512-1517
• 文件大小：229 K

摘要

Consider a graph consisting of a vertex set and an edge set . Let and denote the maximum degree and the chromatic number of , respectively. We say that is equitably -colorable if there exists a proper -coloring of such that the sizes of any two color classes differ by at most one. Obviously, if is equitably -colorable, then . Conversely, even if satisfies , we cannot guarantee that must be equitably -colorable. In 1994, the Equitable -Coloring Conjecture asserts that a connected graph with is equitably -colorable if is different from for all . In this paper, we give necessary conditions for a graph (not necessarily connected) with to be equitably -colorable and prove that those necessary conditions are also sufficient conditions when is a bipartite graph, or satisfies , or satisfies .