Vertex-distinguishing E-total coloring of a complete bipartite graph K9, n (93 ≤ n ≤ 216)
-
摘要: 图
$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-全色数.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. -
表 1
$K_{9,216}$ 的顶点$v_{j}(93\leqslant j \leqslant 106)$ 及其关联边的染色方案Tab. 1 The coloring method of vertex
$v_{j}$ and its incident edges of$K_{9,216}$ when$93\leqslant j \leqslant 106$ 顶点vj 顶点的色集合
(顶点颜色)u1vj
的颜色u2vj
的颜色u3vj
的颜色u4vj
的颜色u5vj
的颜色u6vj
的颜色u7vj
的颜色u8vj
的颜色u9vj
的颜色$v_{93}$ 38(3) 8 8 8 8 8 8 8 8 8 $v_{94}$ 48(4) 8 8 8 8 8 8 8 8 8 $v_{95}$ 58(5) 8 8 8 8 8 8 8 8 8 $v_{96}$ 68(6) 8 8 8 8 8 8 8 8 8 $v_{97}$ 78(7) 8 8 8 8 8 8 8 8 8 $v_{98}$ 13457(7) 4 4 1 3 4 5 4 3 4 $v_{99}$ 13467(7) 4 4 1 4 4 4 6 3 4 $v_{100}$ 23457(7) 4 3 4 2 4 5 4 5 4 $v_{101}$ 23467(7) 4 4 4 2 4 4 6 3 4 $v_{102}$ 134567(7) 5 6 1 5 4 5 4 5 3 $v_{103}$ 234567(7) 6 5 6 2 6 4 6 3 6 $v_{104}$ 123457(7) 3 5 1 2 3 4 3 4 4 $v_{105}$ 123467(7) 3 6 1 2 3 3 3 4 4 $v_{106}$ 1234567(7) 5 4 1 2 3 5 6 4 3 
下载: 导出CSV
表 2
$K_{9, 216}$ 的顶点$v_{j}(107\leqslant j \leqslant 216)$ 及其关联边的染色方案Tab. 2 The coloring method of vertex
$v_{j}$ and its incident edges of$K_{9,216}$ when$107\leqslant j \leqslant 216$ 条件 顶点$v_{j}$的色集合 顶点$v_{j}$及其关联边的颜色 $3\leqslant a\leqslant7$ $\{1, a, 8\}$ $a;8, 8, 1, 8, 8, 8, 8, 8, 8$ $2\leqslant a < b\leqslant7$ $\{a, b, 8\}$ $b;8, 8, 8, 8, 8, 8, 8, 8, a$ $2\leqslant a < b\leqslant7$ $\{1, a, b, 8\}$ $b;8, 8, 1, 8, 8, 8, 8, 1, a$ $2\leqslant a < b < c\leqslant7$ $\{a, b, c, 8\}$ $c;8, 8, 8, a, 8, 8, b, 8, b$ $2\leqslant a < b < c\leqslant7$ $\{1, a, b, c, 8\}$ $c;8, 8, 1, a, 8, 8, a, 1, b$ $2\leqslant a < b < c < d\leqslant7$ $\{a, b, c, d, 8\}$ $d;8, a, b, 8, 8, 8, b, 8, c$ $2\leqslant a < b < c < d\leqslant7$ $\{1, a, b, c, d, 8\}$ $d;8, a, 1, b, 8, 8, 8, 1, c$ $2\leqslant a < b < c < d < e\leqslant7$ $\{a, b, c, d, e, 8\}$ $e;8, a, b, c, 8, 8, 8, 8, d$ $2\leqslant a < b < c < d < e\leqslant7$ $\{1, a, b, c, d, e, 8\}$ $e;8, a, b, c, 8, 8, 8, 1, d$
下载: 导出CSV
-
[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. -
