关于二部图K(m,n)-2的色唯一性

On the Chromaticity of the Bipartite Graph K(m,n)-2

设Ｋ（ｍ，ｎ）－２表示从完全二部图Ｋ（ｍ，ｎ）中删去任意２条边所得之图．本文证明了：１．若ｎ≥ｍ≥３，且ｎ＋ｍ＞（ｎ－ｍ）２＋８＋１２（ｎ－ｍ）２＋４，则Ｋ（ｍ，ｎ）－２是色唯一图；２．当ｍ≥３时，Ｋ（ｍ，ｍ）－２，Ｋ（ｍ，ｍ＋１）－２和Ｋ（ｍ，ｍ＋２）－２均是色唯一图．

Let K(m,n)-2 denote the bipartite graph obtained by deleting two edges from the complete bipartite graph K(m,n) . In this paper, we prove that (1) K(m,n)-2 is chromatically unique if 3≤m≤n and n+m-((n-m) 2+8) 1/2 >(n-m) 2/2+4 . (2) K(m,m)-2, K(m,m+1)-2 and K(m,m+2)-2 are all chromatically unique if m≥3 .