| 摘要: |
| 通过研究一类特殊图的顶点染色，得到了以下结果：给出了〖JB(|〗S〖JB)|〗=p-3且p∈〖JB({〗4,5,〖JB(〗6〖JB)}〗〖JB)〗 ，图G的顶点染色数;证明了〖JB(|〗S〖JB)|〗>〖SX(〗p〖〗2〖SX)〗且〖JB(|〗S〖JB)|〗=p-3的图G不存在第p-m类图，m≥7且m是正整数;证明了〖JB(|〗S〖JB)|〗=p-3时，χ(G)≤4θ(G)+θ2(G)-1;进一步证明了猜想χ(G)≤4θ(G) |
| 关键词: 顶点染色 最大团 第k类图 图的厚度 |
| DOI： |
| 分类号: |
| 基金项目: |
|
| Proof of a Conjecture of A Class of Vertex Coloring of Special Graphs |
|
ZHANG Xiang bo
|
| Abstract: |
| Throughout the study on a class of vertex coloring of special graphs, this paper gives the following results:
(1) Give vertex coloring number of graph G, 〖JB(|〗S〖JB)|〗=p-3and p∈〖JB({〗4,5,〖JB(〗6〖JB)}〗〖JB)〗 .
(2) Prove that graph G of〖JB(|〗S〖JB)|〗>〖SX(〗p〖〗2〖SX)〗 and 〖JB(|〗S〖JB)|〗=p-3has no the p-m class of graph, m≥7and m is positive integer.
(3) Prove that χ(G)≤4θ(G)+θ2(G)-1, when〖JB(|〗S〖JB)|〗=p-3.
All kinds of vertex coloring number of graph G when〖JB(|〗S〖JB)|〗=p-3are given from these results above, and further it is proven that the conjecture χ(G)≤4θ(G)+θ2(G)-1 is right., which provide some thoughts and methods for further study on this conjecture and the graph vertex coloring. |
| Key words: vertex coloring, the maximum clique, thekclass of graph, thickness of a graph |
