Equivalence of two conjectures on equitable coloring of graphs

被引：0

作者：

Bor-Liang Chen

Ko-Wei Lih

Chih-Hung Yen

机构：

[1] National Taichung Institute of Technology,Department of Business Administration

[2] Academia Sinica,Institute of Mathematics

[3] National Chiayi University,Department of Applied Mathematics

来源：

Journal of Combinatorial Optimization | 2013年 / 25卷

关键词：

Equitable coloring; Maximum coloring; -equitable graph; Maximum degree; Independence number;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

A graph G is said to be equitably k-colorable if there exists a proper k-coloring of G such that the sizes of any two color classes differ by at most one. Let Δ(G) denote the maximum degree of a vertex in G. Two Brooks-type conjectures on equitable Δ(G)-colorability have been proposed in Chen and Yen (Discrete Math., 2011) and Kierstead and Kostochka (Combinatorica 30:201–216, 2010) independently. We prove the equivalence of these conjectures.

引用

页码：501 / 504

页数：3

共 10 条

[1] Brooks RL(1941)On colouring the nodes of a network Proc Camb Philos Soc 37 194-197
[2] Chen B-L(1994)Equitable coloring and the maximum degree Eur J Comb 15 443-447
[3] Lih K-W(2008)Chromatic coloring with a maximum color class Discrete Math 308 5533-5537
[4] Wu P-L(2010)Equitable versus nearly equitable coloring and the Chen-Lih-Wu conjecture Combinatorica 30 201-216
[5] Chen B-L(1973)Equitable coloring Am Math Mon 80 920-922
[6] Huang K-C(undefined)undefined undefined undefined undefined-undefined
[7] Yen C-H(undefined)undefined undefined undefined undefined-undefined
[8] Kierstead HA(undefined)undefined undefined undefined undefined-undefined
[9] Kostochka AV(undefined)undefined undefined undefined undefined-undefined
[10] Meyer W(undefined)undefined undefined undefined undefined-undefined

← 1 →