| 稀疏图平方图的染色数上界 |
| |
| 引用本文： | 张艳.稀疏图平方图的染色数上界[J].吉林大学学报(理学版),2020,58(3):575-589. |
| |
| 作者姓名： | 张艳 |
| |
| 作者单位： | 天津大学 应用数学中心, 天津 300072 |
| |
| 摘 要： | 图G的平方G2定义为顶点集V(G)=V(G2), 并且uv∈E(G2)当且仅当u和v之间的距离至多为2. G2的色数χ(G2)是指使得G2存在正常k顶点染色的最小整数k. 用权转移的方法证明: 如果mad(G)<4且Δ(G)≥7, 则χ(G2)≤3Δ(G)+1;
如果mad(G)≤4且Δ(G)≥8, 则χ(G2)≤3Δ(G)+5.
|
| 关 键 词： | k顶点染色 平方图 最大平均度 色数 |
| 收稿时间： | 2019-08-29 |
Upper Bound on Chromatic Number of Square Graph of Sparse Graphs |
| |
| ZHANG Yan.Upper Bound on Chromatic Number of Square Graph of Sparse Graphs[J].Journal of Jilin University: Sci Ed,2020,58(3):575-589. |
| |
| Authors: | ZHANG Yan |
| |
| Institution: | Center for Applied Mathematics, Tianjin University, Tianjin 300072, China |
| |
| Abstract: | The square G2 of a graph G is a graph such that V(G)=V(G2) and uv∈E(G2) if and only if the distance between u and v is at most two. The chromatic number χ(G2) of G2 is the minimum k for which G2 has a proper k vertex coloring. Using the discharging method, the author proves that if mad(G)<4 and Δ(G)≥7, then χ(G2)≤3Δ(G)+1, if mad(G)≤4 and Δ(G)≥8, then χ(G2)≤3Δ(G)+5. |
| |
| Keywords: | k vertex coloring square graph maximum average degree chromatic number |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《吉林大学学报(理学版)》浏览原始摘要信息 |
| 点击此处可从《吉林大学学报(理学版)》下载免费的PDF全文 |
