刘婷,孙磊.关于图的3-条件色数[J].数学研究及应用,2014,34(1):43~48
关于图的3-条件色数
On 3-Hued Coloring of Graphs
投稿时间:2012-07-23  最后修改时间:2013-02-19
DOI:10.3770/j.issn:2095-2651.2014.01.004
中文关键词:  $r$-条件色数  $3$-正常图  三角.
英文关键词:$r$-hued chromatic number  $3$-normal graph  triangle.
基金项目:山东省高等学校科技计划项目(Grant No.J10LA11), 山东省自然科学基金(Grant No.ZR2010AQ003).
作者单位
刘婷 山东师范大学数学科学学院, 山东 济南 250014 
孙磊 山东师范大学数学科学学院, 山东 济南 250014 
摘要点击次数: 1118
全文下载次数: 1430
中文摘要:
      对整数$k>0$, $r>0$,图$G$的一个$(k,r)$-染色是$G$的顶点的一个正常$k$-染色,使得$G$中任意度数为$d$的顶点$v$,其邻域中至少出现$\min\{d,r\}$种不同的颜色.使$G$有一个正常的$(k,r)$-染色的最小$k$值称为$G$的条件色数,记为$\chi_r(G)$.如果 $\chi_r(G)=\chi(G)$,~则称图$G$ 是$r$-正常的.本文主要给出了$3$-正常图的两个充分条件和特殊图类的$3$-条件色数的最好上界.
英文摘要:
      For integers $k>0$, $r>0$, a $(k,r)$-coloring of a graph $G$ is a proper $k$-coloring of the vertices such that every vertex of degree $d$ is adjacent to vertices with at least $\min\{d,r\}$ different colors. The $r$-hued chromatic number, denoted by $\chi_r(G)$, is the smallest integer $k$ for which a graph $G$ has a $(k,r)$-coloring. Define a graph $G$ is $r$-normal, if $\chi_r(G)=\chi(G)$. In this paper, we present two sufficient conditions for a graph to be $3$-normal, and the best upper bound of $3$-hued chromatic number of a certain families of graphs.
查看全文  查看/发表评论  下载PDF阅读器