刘林忠,李引珍,张忠辅.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); 兰州交通大学青蓝基金 |
|
摘要点击次数: 2792 |
全文下载次数: 1859 |
中文摘要: |
图$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阅读器 |
|
|
|