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

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

中文关键词:  完全二部图  色唯一图  色划分

英文关键词:complete bipartite graph  chromatically unique graph  partition into color class.

中文摘要:

      设Ｋ（ｍ，ｎ）－２表示从完全二部图Ｋ（ｍ，ｎ）中删去任意２条边所得之图．本文证明了：１．若ｎ≥ｍ≥３，且ｎ＋ｍ＞(（ｎ－ｍ）^２＋８)^1/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-(（ｎ－ｍ）^２＋８)^1/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 .