全着色公平性与图染色问题中完全r-部p-平衡图的均匀全染色

≤≤≤≤可在www.sciencedirect.com在线获取理论计算机科学电子笔记346（2019）685-697www.elsevier.com/locate/entcs图Kr×p对于pEven1安德森湾达席尔瓦2DM AT，Ponti f'ıciaUniversidadeCat'oli cadoRiodeJanei ro，B razil.Simone Dantas2IME，巴西弗鲁米嫩塞联邦大学。戴安娜佐佐木2IME，巴西里约热内卢州大学摘要如果被任何两种不同颜色着色的元素的数量最多相差一个，则全着色是公平的。图的均匀全染色数（χ′e′）是使图具有均匀全染色的最小整数。Wang（2002）证明了Δ + 1 χ′e′Δ + 2。1994年，Fu证明了所有奇阶完全r-部p-平衡图都存在均匀（Δ + 2）-全染色.对于偶数情形，他确定χ′e′ Δ+ 3。Silva，Dantas and Sasaki（2018）在G是完全r -部p -平衡图的情况下验证了Wang的猜想，证明了如果G的阶数为奇数，则χ ′ e ′ = Δ + 1，Δ +2如果G是偶数阶。本文通过证明当G是完备的时χ′e′= Δ + 1改进了这个界r-部p-平衡图，其中r≥4为偶数，p为偶数，且对r为奇数，p为偶数。关键词：均匀全染色，完全r-部p-平衡图，图染色.1引言本文所分析的所有图都是有限的、无向的和简单的。 设G=（V，E）是一个图.图G的k-全染色是指图G的顶点和边被赋予k种颜色，使得相邻或关联的元素具有不同的颜色。G的全色数，记为χJJ，是G有一个最小的k1 本 研 究 部 分 由 CoordenalécéréaodeAperfeicérécoamentodePessoaldeN'estuvelSuperior-Brasil （ CAPES ） - FinanceCode 001、CNPq、FAPERJ（巴西研究机构）和L' oreal-UNESCO- ABC P ara m ulheres na C i pérés 2017资助。2电子邮件：andersongs@mat.puc-rio.br，sdantas@id.uff.br，diana. ime.uerj.br。https://doi.org/10.1016/j.entcs.2019.08.0601571-0661/© 2019作者。出版社：Elsevier B.V.这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。686A.G. da Silva等人/理论计算机科学电子笔记346（2019）685−−k-全着色。从全染色的定义出发，我们得到了χJJ≥ Δ+1和全染色猜想（TCC）（Behzad [2]，Vizing [13]），指出任何图的全色数至多为Δ +2，其中Δ是图的最大度。1989年，S′anchez-Arroyo[10]证明了任意图的全色数的确定问题是NP-难的，即使对于三次二部图也是NP-难的.公平全染色是满足任何两个色类的基数之间的差至多为1的附加性质的全染色图G的均匀全色数记为χJEJ，是使G具有均匀全染色的最小整数.在2002年，Wang[14]证明了任意图的均匀全色数至多为Δ+ 2（均匀全色数猜想（ETCC））。从那时起 ， 许 多 论 文 已 经 发 表 在 这 个 主 题 [5 ， 7 ， 8] 。 在 2016 年 ， Dantas ， deFigueiredo，Mazzuoccolo，Preissmann，dos Santos和Sasaki[5]证明了确定三次二部图的公平全色数的问题是NP-完全的。1974年，Bermond[3]确定了所有完全r-部p-平衡图的全色数。完全r-部p-平衡图，记作Kr×p，是指顶点集可划分为r个独立集X1，···，Xr，使得|X i|=p，i=1，...，r，且不同部分的任意两个顶点之间存在一条边。1994年，Fu [6]确定了完全二部图的均匀全染色为Δ +2，并证明了所有奇阶完全r部图都存在均匀（Δ+2）-全染色。Silva，Dantas和Sasaki [11]确定了两类完全r-部p-平衡图的公平全色数：r≥4偶且p奇（χJEJ= Δ +2）和r且p奇（χJEJ= Δ +1）.本文改进了已有的上界，证明了当图是完全r-部p-平衡图，且r≥4为偶数且p为偶数，或r为奇数且p为偶数时，上界χJEJ2预赛对于完全r-部p-平衡图，我们采用如下的约定. Kr×p的顶点的显示类似于一个具有r列和p行的矩阵，其中每列表示顶点集的划分的一部分Xi 顶点xij是部分Xi的第j个顶点，它被分配给第j 行和第i列。我们将水平边定义为边xij xi′j（见图1c）。此外，行j和jJ之间的距离l的匹配（1 ≤j

下载后可阅读完整内容，剩余1页未读，立即下载