华东师范大学学报（自然科学版） >

2020 , Vol. 2020 >Issue 6: 24 - 29

DOI: https://doi.org/10.3969/j.issn.1000-5641.201911028

数学

完全二部图K9, n (93 ≤ n ≤ 216)的点可区别E-全染色

  • 陈祥恩 ,
  • 杨伟光
展开
  • 西北师范大学 数学与统计学院, 兰州 730070
陈祥恩, 男, 教授, 硕士研究生导师, 研究方向为图论及其应用. E-mail: chenxe@nwnu.edu.cn

收稿日期: 2019-06-26

  网络出版日期: 2020-12-01

基金资助

国家自然科学基金(11761064, 61163037)

收起

Vertex-distinguishing E-total coloring of a complete bipartite graph K9, n (93 ≤ n ≤ 216)

  • CHEN Xiang’en ,
  • YANG Weiguang
Expand
  • College of Mathematics and Statistics, Northwest Normal University, Lanzhou 730070, China

Received date: 2019-06-26

  Online published: 2020-12-01

Fold

摘要

图$G$的一个E-全染色是指使相邻点染以不同颜色且每条关联边与它的端点染以不同颜色的全染色. 对图$G$的一个E-全染色$f$, 一旦$\forall u, v\in V(G), u\neq v$, 就有$C(u)\neq C(v)$, 其中$C(x)$表示在$f$下点$x$的颜色以及与$x$关联的边的颜色所构成的集合, 则$f$称为图$G$的点可区别的E-全染色, 简称VDET染色. 令$\chi _{vt}^{e}(G)=\min\{k: G {\text{存在}} k{\text{\rm{-}}}{\rm{VDET}} {\text{染色}}\},$ 称$\chi _{vt}^{e}(G)$为图$G$的点可区别E-全色数. 本文利用反证法、组合分析法及构造具体染色等方法, 讨论并给出了完全二部图$K_{9, n}\; (93\leqslant n\leqslant 216)$的点可区别E-全色数.

关键词： 完全二部图; E-全染色; 点可区别E-全染色; 点可区别E-全色数

本文引用格式

陈祥恩 , 杨伟光 . 完全二部图K9, n (93 ≤ n ≤ 216)的点可区别E-全染色[J]. 华东师范大学学报（自然科学版）, 2020 , 2020(6) : 24 -29 . DOI: 10.3969/j.issn.1000-5641.201911028

Abstract

Let $G$ be a simple graph. A total coloring $f$ of $G$ is called an E-total coloring if no two adjacent vertices of $G$ receive the same color, and no edge of $G$ receives the same color as one of its endpoints. For an E-total coloring $f$ of a graph $G$, if $C(u)\neq C(v)$ for any two distinct vertices $u$ and $v$ of $V(G)$, where $C(x)$ denotes the set of colors of vertex $x$ and of the edges incident with $x$ under $f$, then $f$ is called a vertex-distinguishing E-total coloring of $G$. Let $\chi _{vt}^{e}(G)=\min\{k: G$ has a $k$-VDET coloring$\}.$ Then, $\chi _{vt}^{e}(G)$ is called the VDET chromatic number of $G$. By using contradiction, the method of a combinatorial analysis and the method of constructing specific coloring, the VDET coloring of a complete bipartite graph $K_{9, n}$ is discussed and the VDET chromatic number of $K_{9, n}\; (93\leqslant n\leqslant 216)$ is determined.

Key words： complete bipartite graph; E-total coloring; vertex-distinguishing E-total coloring; vertex-distinguishing E-total chromatic number

参考文献

[1] HARARY F, PLANTHOLT M. The point-distinguishing chromatic index [M]// Graphs and Application. New York: Wiley Interscience, 1985: 147-162.
[2] HORŇÁK M, SOTÁK R. The fifth jump of the point-distinguishing chromatic index of Kn,n [J]. Ars Combinatoria, 1996, 42: 233-242
[3] HORŇÁK M, SOTÁK R. Localization jumps of the point-distinguishing chromatic index of Kn,n [J]. Discuss Math Graph Theory, 1997, 17: 243-251
[4] HORŇÁK M, SALVI N Z. On the point-distinguishing chromatic index of complete bipartite graphs [J]. Ars Combinatoria, 2006, 80: 75-85
[5] SALVI N Z. On the point-distinguishing chromatic index of Kn,n [J]. Ars Combinatoria, 1988, 25B: 93-104
[6] SALVI N Z. On the value of the point-distinguishing chromatic index of Kn,n [J]. Ars Combinatoria, 1990, 29B: 235-244
[7] CHEN X E, ZU Y, ZHANG Z F. Vertex-distinguishing E-total colorings of graphs [J]. Arab J Sci Eng, 2011, 36: 1485-1500
[8] CHEN X E, ZU Y. Vertex-distinguishing E-total coloring of the graphs mC3 and mC4 [J]. Journal of Mathematical Research & Exposition, 2011, 31: 45-58
[9] 李世玲, 陈祥恩, 王治文. 完全二部图 $\scriptstyle{K_{3, n}(3\leqslant n\leqslant 17)}$ 的点可区别E-全染色 [J]. 吉林大学学报(理学版), 2015, 53(6): 1171-1176
[10] 李世玲, 陈祥恩, 王治文. 完全二部图 $\scriptstyle{K_{3, n}(n\geqslant 18)}$ 的点可区别E-全染色 [J]. 山东大学学报(理学版), 2015, 51(4): 68-71
[11] 李世玲. 完全二部图的点可区别E-全染色的若干结果 [D]. 兰州: 西北师范大学, 2017.
[12] CHEN X E. Vertex-distinguishing E-total coloring of complete bipartite graph \scriptsize $ {K_{7, n}} $ \normalsize when \scriptsize $ {7\leqslant n\leqslant 95} $ \normalsize [J]. Communications in Mathematical Research, 2016, 32(4): 359-374
[13] 杨伟光, 陈祥恩. 完全二部图$\scriptstyle{K_{9, n}(9\leqslant n\leqslant 92)}$的点可区别E-全染色[J]. 吉林大学学报(理学版), 2020, 58(2): 301-308.
Options
文章导航

/

〈 〉