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

首页   |   关于   |   浏览   |   投稿指南   |   新闻公告
数学进展 - 2020, Vol. 49(6): 675-684
研究论文
平面图的单射边染色
Injective Edge Coloring of Planar Graphs

卜月华1, 2, 齐晨涛1, 朱俊蕾3
BU Yuehua1, 2, QI Chentao1, ZHU Junlei3

1. 浙江师范大学数学与计算机科学学院, 金华, 浙江, 321004;
2. 浙江师范大学行知学院, 金华, 浙江, 321004;
3. 嘉兴学院数理与信息工程学院, 嘉兴, 浙江, 314001
1. College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua, Zhejiang, 321004, P. R. China;
2. Zhejiang Normal University Xingzhi College, Jinhua, Zhejiang, 321004, P. R. China;
3. College of Mathematics, Physics and Information Engineering, Jiaxing University, Jiaxing, Zhejiang, 314001, P. R. China

收稿日期: 2019-08-16
出版日期: 2020-11-17
2020, Vol. 49(6): 675-684
DOI: 10.11845/sxjz.2019089b


PDF
[343 KB]
124
下载
218
浏览

引用导出
0
    /   /   推荐

摘要 图$G$的$k$-单射边染色是指映射f: E(G)$\rightarrow \{1,2,\cdots,k\}$, 若$e_{1}$, $e_{2}$和$e_{3}$ 是G 中的连续边, 则$f(e_1)\neq f(e_3)$. 称$\chi'_{i}(G)=\min\{k\,|\,G\,\mbox{存在}\,k\mbox{-单射边染色}\}$为图的单射边染色数. 本文证明了: 对$g(G)\geq6$的平面图G, 有 $\chi_i'(G)\leq3\Delta(G)-2$, 对$g(G)\geq26$且$\Delta(G)\leq3$ 的平面图G, 有$\chi_i'(G)\leq4$, 对$g(G)\geq16$且$\Delta(G)\geq4$的平面图G, 有 $\chi_i'(G)\leq\Delta(G)+1$, 其中g(G)表示平面图G的围长.
关键词 平面图单射边染色围长最大度    
Abstract:A k-injective edge coloring of a graph G is a mapping f: E(G)$\rightarrow \{1,2,\cdots,k\}$ such that if $e_{1}, e_{2}$ and $e_{3}$ are consecutive edges in G, then $f(e_1)\neq f(e_3)$. $\chi'_{i}(G)=\min\{k\,|\,G$ has a $k$-injective edge coloring$\}$ is called the injective edge coloring number. In this paper, we prove that for a planar graph $G$ with maximum degree $\Delta$, $\chi_i'(G)\leq3\Delta-2$ if g(G)$\geq6$; $\chi_i'(G)\leq4$ if $g(G)\geq$26 and $\Delta\leq3$; $\chi_i'(G)\leq\Delta+1$ if $g(G)\geq16$ and $\Delta\geq4$, where g(G) denotes the girth of G.
Key wordsplanar graph    injective-edge coloring    girth    maximum degree
PACS:  O157.5  
[1] Alon N.,Combinatorial Nullstellensatz, Combin. Probab. Comput., 1999, 8(1/2): 7-29.
[2] Bu Y.H. and Qi C.T., Injective edge coloring of sparse graphs, Discrete Math. Algorithms Appl., 2018, 10(2): 1850022, 16 pp.
[3] Cardoso D.M., Cerdeira J.O., Cruz J.P. and Dominic C., Injective edge chromatic index of a graph,2015, arXiv:1510.02626.
[4] Hahn G.,Kratochv$\acute{i}$l, J., $\check{S}$ir$ \acute{a} \check{n}$, J. and Sotteau, D., On the injective chromatic number of graphs, Discrete Math., 2002, 256(1/2): 179-192.
[1] 雷辉, 史永堂. 图的星边染色综述[J]. 数学进展, 2021, 50(2): 77-93.
[2] 陈敏, 余梦蕾, 李柏翰, 范佳清. 外平面图的弱边面染色[J]. 数学进展, 2020, 49(2): 165-171.
[3] 关夏夏, 吴楚雄, 杨卫华, 孟吉翔. 平面图书式嵌入综述[J]. 数学进展, 2020, 49(1): 1-12.
[4] 卜月华,王丽霞. 稀疏平面图的2-距离染色[J]. 数学进展, 2019, 48(2): 145-155.
[5] 王茂群, 杨卫华. 原图是平面图的4-连通线图的哈密尔顿连通性[J]. 数学进展, 2019, 48(1): 29-34.
[6] 卜月华, 叶飘飘. 围长至少为 $\mathbf{5}$ 的平面图的 $\mathrm{\mathbf{injective}}$-染色[J]. 数学进展, 2018, 47(3): 363-372.
[7] 邓兴超, 宋贺, 苏贵福, 田润丽. 小直径二连通外平面图的彩虹连通数[J]. 数学进展, 2018, 47(3): 373-382.
[8] 卜月华, 商春慧. 不含4-圈平面图的2-距离染色[J]. 数学进展, 2017, 46(3): 342-354.
[9] 李晓艳,陈敏,王应前. 关于无5-, 6-及7-圈的平面图的3-可选性[J]. 数学进展, 2016, 45(4): 491-499.
[10] 景昱波,王应前. 可平面图的线性2-荫度的新上限[J]. 数学进展, 2016, 45(2): 185-189.
[11] 卜月华,严晓燕. 不含3, 4, 8-圈的平面图的2-距离染色[J]. 数学进展, 2015, 44(2): 208-218.
[12] 卜月华,严晓燕. 不含3, 4, 8-圈的平面图的2-距离染色[J]. 数学进展, 2014, 43(7): 13055-.
[13] 袁西英;. 关于双圈图的拉普拉斯谱半径的注记(英文)[J]. 数学进展, 2010, 39(6): 703-708.
[14] 董广华;刘彦佩;. 不含三角形的图的最大亏格的下界(英文)[J]. 数学进展, 2009, 38(6): 692-698.
[15] 魏二玲;刘彦佩;. (邻接)树图的同构及平面性[J]. 数学进展, 2009, 38(2): 220-226.
Viewed
Full text


Abstract

Cited

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


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