A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
A Short Proof of the Hajnal–Szemerédi Theorem on Equitable Colouring
复制标题
DOI：
10.1017/s0963548307008619
复制
发表时间：
2008-03
期刊：
影响因子：
--
通讯作者：
H. Kierstead;A. Kostochka
中科院分区：
文献类型：
--
作者：
H. Kierstead;A. Kostochka
如果颜色类的大小相差至多一个，则图的适当顶点着色是公平的。我们给出了著名的Hajal-Szemerédi定理的一个新的较短的证明：对于每个正整数r，每个最大度至多r的图都有r+1个色的均匀着色。证明给出了这种着色的多项式时间算法。
A proper vertex colouring of a graph is equitable if the sizes of colour classes differ by at most one. We present a new shorter proof of the celebrated Hajnal–Szemerédi theorem: for every positive integer r, every graph with maximum degree at most r has an equitable colouring with r+1 colours. The proof yields a polynomial time algorithm for such colourings.