苏克义,陈祥恩.关于完全三部图色唯一性的一个注记[J].数学研究及应用,2010,30(2):233~240
关于完全三部图色唯一性的一个注记
A Note on Chromatic Uniqueness of Completely Tripartite Graphs
投稿时间:2008-01-14  最后修改时间:2008-07-07
DOI:10.3770/j.issn:1000-341X.2010.02.005
中文关键词:  完全三部图  色多项式  色唯一性  色划分.
英文关键词:complete tripartite graph  chromatic polynomial  chromatic uniqueness  color partition.
基金项目:国家自然科学基金(Grant No.10771091),甘肃省教育厅科研项目(Grant No.0501-02).
作者单位
苏克义 银川第六中学, 宁夏 银川 750011; 西北师范大学数学与信息科学学院, 甘肃 兰州 730070 
陈祥恩 西北师范大学数学与信息科学学院, 甘肃 兰州 730070 
摘要点击次数: 1917
全文下载次数: 1520
中文摘要:
      用$P(G,\lambda)$表示简单图$G$的色多项式, 若对任意的简单图$H$,当$P(G,\lambda)=P(H,\lambda)$时都有$H$同构于$G$,则称图$G$是色唯一的.很多学者已得到了一些特殊的完全三部图色唯一的许多充分条件.尤其在2003年, 邹辉文得到: 设$n,k,m$是非负整数, 若$n>\frac{1}{3}m^{2} \frac{1}{3}k^{2} \frac{1}{3}mk \frac{1}{3}m-\frac{1}{3}k \frac{2}{3} \sqrt{m^{2} k^{2} mk}$,则完全三部图$K(n-m,n,n k)$是色唯一的. 本文得到: 设$n,k,m$为非负整数,其中$m\geq2, k\geq0$,若$n\geq\frac{1}{3}m^{2} \frac{1}{3}k^{2} \frac{1}{3}mk \frac{1}{3}m-\frac{1}{3}k \frac{4}{3}$,则完全三部图$K(n-m,n,n k)$是色唯一的. 它是对上述结果在$m\geq2,k\geq0$时的一个改进. 同时还给出了一个相关猜想.
英文摘要:
      Let $P(G,\lambda)$ be the chromatic polynomial of a simple graph $G.$ A graph $G$ is chromatically unique if for any simple graph $H,$ $P(H,\lambda)=P(G,\lambda)$ implies that $H$ is isomorphic to $G$. Many sufficient conditions guaranteeing that some certain complete tripartite graphs are chromatically unique were obtained by many scholars. Especially, in 2003, Zou Hui-wen showed that if $n>\frac{1}{3}m^{2} \frac{1}{3}k^{2} \frac{1}{3}mk \frac{1}{3}m-\frac{1}{3}k \frac{2}{3} \sqrt{m^{2} k^{2} mk}$, where $n,k$ and $m$ are non-negative integers, then the complete tripartite graph $K(n-m,n,n k)$ is chromatically unique (or simply $\chi$--unique). In this paper, we prove that for any non-negative integers $n, m$ and $k,$ where $m\geq2$ and $k\geq0,$ if $n\geq\frac{1}{3}m^{2} \frac{1}{3}k^{2} \frac{1}{3}mk \frac{1}{3}m-\frac{1}{3}k \frac{4}{3}$, then the complete tripartite graph $K(n-m,n,n k)$ is $\chi$--unique, which is an improvement on Zou Hui-wen's result in the case $m\geq2$ and $k\geq0.$ Furthermore, we present a related conjecture.
查看全文  查看/发表评论  下载PDF阅读器