刘林忠,李引珍,张忠辅.Halin-图的点强全染色[J].数学研究及应用,2006,26(2):269~275
Halin-图的点强全染色
On the Vertex Strong Total Coloring of Halin-Graphs
投稿时间:2004-05-25  
DOI:10.3770/j.issn:1000-341X.2006.02.012
中文关键词:  Halin-图  图染色  点强全染色  全染色.
英文关键词:Halin-graph  coloring problem  vertex strong total coloring  total coloring problem.
基金项目:国家自然科学基金 (No.19871036); 兰州交通大学青蓝基金
作者单位
刘林忠 兰州交通大学交通运输学院, 甘肃 兰州 730070
清华大学数学科学系, 北京 100084 
李引珍 兰州交通大学交通运输学院, 甘肃 兰州 730070 
张忠辅 兰州交通大学数理学院, 甘肃 兰州 730070 
摘要点击次数: 2779
全文下载次数: 1846
中文摘要:
      图$G(V,E)$的一个$k$-正常全染色$f$叫做一个$k$-点强全染色当且仅当对任意$v\in V(G)$, $N[v]$中的元素被染不同色, 其中$N[v]=\{u|uv\in V(G)\}\bigcup \{v\}$. $\chi^{vs}_T(G)=\min\{k|$存在图$G$的$k$-点强全染色\}叫做图$G$的点强全色数. 对3-连通平面图$G(V,E)$, 如果删去面$f_0$边界上的所有点后的图为一个树图, 则$G(V,E)$叫做一个Halin-图. 本文确定了最大度不小于6的Halin-图和一些特殊图的的点强全色数$\chi^{vs}_T(G)$, 并提出了如下猜想: 设$G(V,E)$为每一连通分支的阶不小于6的图, 则$\chi^{vs}_T(G)\leq \Delta (G)+2$, 其中 $\Delta (G)$为图$G(V,E)$的最大度.
英文摘要:
      A proper $k$-total coloring $f$ of the graph $G(V,E)$ is said to be a $k$-vertex strong total coloring if and only if for every $v\in V(G)$, the elements in $N[v]$ are colored with different colors, where $N[v]=\{u|uv\in V(G)\}\cup \{v\}$. The value $\chi^{vs}_T(G)=\min\{k|$ there is a $k$-vertex strong total coloring of $G\}$ is called the vertex strong total chromatic number of $G$. For a 3-connected plane graph $G(V,E)$, if the graph obtained from $G(V,E)$ by deleting all the edges on the boundary of a face $f_0$ is a tree, then $G(V,E)$ is called a Halin-graph. In this paper, $\chi^{vs}_T(G)$ of the Halin-graph $G(V,E)$ with $\Delta (G)\geq 6$ and some special graphs are obtained. Furthermore, a conjecture is initialized as follows: Let $G(V,E)$ be a graph with the order of each component are at least 6, then $\chi^{vs}_T(G)\leq \Delta (G)+2$, where $\Delta (G)$ is the maximum degree of $G$.
查看全文  查看/发表评论  下载PDF阅读器