几类图的邻点可区别关联色数

Adjacent vertex distinguishing incidence chromatic numbers of some graphs

摘要

邻点可区别关联着色是要求任何相邻顶点具有不同色集的关联着色。文章基于已有的研究结果,分别研究圈、路、轮、扇、星、完全图和部分完全二部图的Mycielski图的邻点可区别关联着色、路与偶圈的笛卡尔积图、星与圈(5圈除外)的笛卡尔积图的邻点可区别关联着色,利用构造着色的方法,分别确定其色数。结果表明:这些图类的邻点可区别关联色数均小于或等于最大度加2。

Abstract

An adjacent vertex distinguishing incidence coloring of a graph is an incidence coloring such that no pair of adjacent vertices have the same set of colors. Based on some previous research results, this paper studies the adjacent vertex distinguishing incidence coloring of Mycielski graphs of path, cycle, star, fan, wheel, complete graph and some complete bipartite graph, respectively. It also studies the adjacent vertex distinguishing incidence coloring of Cartesian product of path and even cycle, Cartesian product of star and cycle (except 5 cycle). Using the method of structural coloring, their chromatic numbers are determined, respectively. The results show that the adjacent vertex distinguishing incidence chromatic numbers of these graph classes are less than or equal to the maximum degree plus 2.

关键词

Mycielski图 / 关联着色 / 邻点可区别关联着色 / 邻点可区别关联色数

Key words

Mycielski graph / incidence coloring / adjacent vertex distinguishing incidence coloring / adjacent vertex distinguishing incidence chromatic number

参考文献

[1] 王雅琴 . 图的关联着色与邻点可区别关联着色[D]. 青岛: 山东科技大学, 2007: 13-18.

[2] 王文丽, 刘西奎, 周薇 . 关于图的广义Mycielski图的邻点可区别关联着色[J]. 山东大学学报(理学版), 2008, 43(10): 77-79.

[3] 王倩, 田双亮 . 若干联图的邻点可区别关联染色[J]. 山东大学学报(理学版), 2011, 46(8): 89-91.

[4] 董桂香, 张丽 . Cartesian积图的关联色数与邻点可区别关联色数[J]. 黑龙江大学自然科学学报, 2016, 33(4): 462-465.

[5] 张丽, 张霞 . 花图的邻点可区别关联色数[J]. 黑龙江大学自然科学学报, 2010, 27(4): 435-439.

[6] 张丽, 陈宏宇, 袁西英 . 一类4-正则平面图的邻点可区别关联色数[J]. 数学的实践与认识, 2012, 42(19): 197-201.

[7] 刘卓雅, 徐常青 . 无相交三角形平面图的邻点可区别边染色[J]. 山东大学学报(理学版), 2020, 55(9): 36-41.

[8] 蔡洪锋, 黄丹君 . 无相邻3-圈平面图的邻点可区别边染色[J]. 浙江师范大学学报(自然科学版), 2022, 45(4): 361-367.

[9] 张小秀, 黄丹君 . 围长至少为5的平面图的邻点可区别边染色[J]. 数学学报(中文版), 2022, 65(2): 325-334.

[10] 霍京京, 王艺桥 . 最大度为6的图的邻点可区别边色数[J]. 应用数学学报, 2018, 41(6): 788-800.

[11] 刘卓雅 . IC-平面图的邻点可区别边染色[D]. 天津: 河北工业大学, 2021: 5-9.

[12] 杨腾飞, 徐常青 . 围长至少为5的IC-可平面图的邻点可区别边染色[J]. 数学的实践与认识, 2022, 52(10): 179-183.

[13] 李锦, 徐长青 . 不含相交三角形IC-可平面图的邻点可区别边染色[J]. 山东大学学报(理学版), 2023, 58(12): 134-139.

[14] Brualdi R A, Quinn Massey J J . Incidence and strong edge colorings of graphs[J]. Discrete Mathematics, 1993, 122(1/2/3): 51-58.

[15] 张婷, 朱恩强, 赵双柱, 等 . 若干Mycielski图邻点可区别I-均匀全染色[J]. 大连理工大学学报, 2018, 58(5): 547-550.

基金资助

山东省自然科学基金项目(ZR2021QA062)