Please wait a minute...
北京大学期刊网 | 作者  审稿人  工作人员

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 2018, Vol. 47(3): 363-372
研究论文
围长至少为 $\mathbf{5}$ 的平面图的 $\mathrm{\mathbf{injective}}$-染色
Upper Bounds for the Injective Coloring of Planar Graphs with Girth at Least 5

卜月华1,2,*, 叶飘飘1
BU Yuehua1,2, YE Piaopiao1

1. 浙江师范大学数理信息学院, 金华, 浙江, 321004;
2. 浙江师范大学行知学院, 金华, 浙江, 321004
1. College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua, Zhejiang, 321004, P. R. China;
2. Zhejiang Normal University Xingzhi College, Jinhua, Zhejiang, 321004, P. R. China

收稿日期: 2016-10-11
出版日期: 2018-06-01
2018, Vol. 47(3): 363-372
DOI: 10.11845/sxjz.2016118b


PDF
[364 KB]
8
下载
49
浏览

引用导出
E-mail这篇文章
E-mail提醒
RSS订阅

摘要 图 $G$ 的 $\mathrm{injective}$ $k$-染色是指映射 $c$: $V(G)\rightarrow\{1,2,\cdot\cdot\cdot,k\}$, 使有公共邻点的两个顶点 $u,v$ 满足 $c(u)\neq c(v)$, 用 $\chi_i(G)$ 表示使 $G$ 有一个 $\mathrm{injective}$ $k$-染色的最小正整数 $k$. 对 $g(G)\geq 5$ 的平面图 $G$, 若 $\Delta(G)\geq20$, 证明了 $\chi_{i}(G)\leq \Delta+3$.
关键词 平面图围长injective 染色    
Abstract:An $\mathrm{injective}$ coloring of graph is a vertex coloring where any two vertices with a common neighbor receive distinct colors. Let $G$ be a planar graph with $g(G)\geq5$ with the $\mathrm{injective}$ chromatic number $\chi_i(G)$. In this paper, we improve some known results by proving that $\chi_i(G)\leq\Delta+3$ if $\Delta(G)\geq20$.
Key wordsplanar graph    girth    $\mathrm{injective}$ coloring    face
PACS:  O157.5  
基金资助:国家自然科学基金 (No. 11771403).
通讯作者: E-mail: $*$ yhbu@zjnu.edu.cn   
[1] Bu, Y.H., Chen, D., Raspaud, A. and Wang, W., Injective coloring of planar graphs, Discrete Appl. Math., 2009, 157(4): 663-672.
[2] Bu, Y.H. and Lu, K., List injective coloring of planar graphs with girth $5,6,8$, Discrete Appl. Math., 2013, 161(10/11): 1367-1377.
[3] Cranston, D., Kim, S. and Yu, G.X., Injective colorings of graphs with low average degree, Algorithmica, 2010, 60(3): 553-568.
[4] Cranston, D., Kim, S. and Yu, G.X., Injective colorings of sparse graphs, Discrete Math., 2010, 310(21): 2965-2973.
[5] Dong, W. and Lin, W.S., Injective coloring of planar graphs with girths 6, Discrete Math., 2013, 313(12): 1302-1311.
[6] Dong, W. and Lin, W.S., Injective coloring of planar graphs with girths 5, Discrete Math., 2014, 315/316(12): 120-127.
[7] Doyon, A., Hahn, G. and Raspaud, A., Some bounds on the $\mathrm{injective}$ chromatic number of graphs, Discrete Math., 2012, 310(6): 585-590.
[8] Hahn, G., Kratochvíl, J., Sirán, J. and Sotteau, D., On the injective chromatic number of graphs, Discrete Math., 2002, 256(1/2): 179-192.
[9] Li, R. and Xu, B.G., Injective choosability of planar graphs of girth five and six, Discrete Math., 2012, 312(9): 1260-1265.
[10] LuŽar, B., Skrekovski, S. and Tancer, M., Injective colorings of planar graphs with few colors, Discrete Math., 2009, 309(18): 5636-5649.
[1] 刘珊, 贺群. Randers空间中的常旗曲率旋转超曲面[J]. 数学进展, 2018, 47(1): 109-116.
[2] 吴亚东. 凸区域上的$p$-阶特征函数及相关的度量[J]. 数学进展, 2018, 47(1): 95-108.
[3] 卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354.
[4] 朱鹏. 空间形式中具有常平均曲率的超曲面的特征值估计[J]. 数学进展, 2017, 46(1): 133-140.
[5] 柯华忠. 论开KdV方程簇与Virasoro约束的一个几何解[J]. 数学进展, 2017, 46(1): 91-96.
[6] 邱双月,王 欢. 维数不超10000的欧氏空间中2个同心球面上紧欧氏11-设计的非存在性[J]. 数学进展, 2016, 45(6): 899-911.
[7] 李晓艳,陈敏,王应前. 关于无5-, 6-及7-圈的平面图的3-可选性[J]. 数学进展, 2016, 45(4): 491-499.
[8] 陈小民. 关于共形Sasaki流形的注记[J]. 数学进展, 2016, 45(4): 610-624.
[9] 景昱波,王应前. 可平面图的线性2-荫度的新上限[J]. 数学进展, 2016, 45(2): 185-189.
[10] 朱晴晴,杨标桂. 近凯勒流形中一般子流形的淹没[J]. 数学进展, 2016, 45(2): 271-289.
[11] 胡传峰, 姬秀. F-相对极值超曲面的Bernstein性质[J]. 数学进展, 2016, 45(1): 143-152.
[12] 卜月华,严晓燕. 不含3, 4, 8-圈的平面图的2-距离染色[J]. 数学进展, 2015, 44(2): 208-218.
[13] 姬秀,胡传峰. \mbox{\boldmath $\mathbb{R}^{5}$}\ 中的Laguerre等参超曲面[J]. 数学进展, 2015, 44(1): 117-127.
[14] 卜月华,严晓燕. 不含3, 4, 8-圈的平面图的2-距离染色[J]. 数学进展, 2014, 43(7): 13055-.
[15] 唐素芳. 半空间上与高阶Laplace算子相对应的积分方程组[J]. 数学进展, 2014, 43(6): 942-950.
Viewed
Full text


Abstract

Cited

  Discussed   
首页 · 关于 · 关于OA · 法律公告 · 收录须知 · 联系我们 · 注册 · 登录


© 2015-2017 北京大学图书馆 .