Equitable Total Coloring of Kn(o)del Graph WΔ,n

来源 :2014全国理论计算机科学学术年会 | 被引量 : 0次 | 上传用户:liangzi_li
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
  A k-total coloring of a graph G is a map σ: V (G)∪E(G)→{1,2,...,k} such that no two adjacent or incident elements of V(G)∪E(G) receive the same color.The total chromatic number is the smallest one out of all the k such that G has a k-total coloring.A k-total coloring is equitable if ‖σ-1(i)|-|σ-1(j)‖≤1 for each pair of distinct colors i and j (1≤i,j≤k).The smallest one out of all the k for which G has an equitable total k-coloring is named equitable total chromatic number.It is known that the problem of determining the total chromatic number is NP-hard,and it remains NP-hard for Δ-regular bipartite graphs with Δ≥3.In this paper,we show that the equitable total chromatic number of Kn(o)del Graph WΔ,n is Δ+1 while Δ=3,4,5 for all even n≥2Δ except W3,10.The result determines the total chromatic numbers of Kn(o)del graphs W3,n,W4,n,and W5,n,also is relevant as an evidence that every regular graph with Δ≤5 is such that the total chromatic number is equal to the equitable total chromatic number.
其他文献
植物生理学是研究植物生命活动规律及其与环境相互关系的科学.与植物、环境相关的学科都与植物生理学有密切联系.因此,植物生理学是植物、农学、蔬菜、果树、林学、园艺、植
会议
现代主义油画是指二十世纪区别于现实主义流派的油画,大致包含后印象主义、野兽派、立体派、未来派、达达派、表现派、超现实主义、抽象主义等流派。这些流派面貌各异,但是通
  六堡茶是后发酵茶,属于类似普洱茶的黑茶,其外形色泽黑褐,汤色红浓明亮,滋味醇和爽口,分为紧压茶和散茶。本研究试图比较不同年份六堡茶的理化性质,从而丰富六堡茶加工理论,为提
由国家计委、科技部共同编制的《当前优先发展的高技术产业化重点领域指南》近日正式向社会公布。这是我国第一部引导高技术产业化发展的指导性文件。在这份指南中有138个领域被
  Over past decades,there has been more and more large scale sensors deployed in a wide range of application areas.Due to the innate imprecision of sensor obs
会议
以外源亚精胺处理NaCl胁迫下毕氏海蓬子幼苗,研究了外源亚精胺对NaCl胁迫下毕氏海蓬子生长、抗氧化酶活性及光合特性的影响.结果表明,300mmol·L-1NaCl浓度最适宜毕氏海蓬子
  以休眠期的马蹄莲小块茎为试材,进行马蹄莲的脱菌试验.接种前采用种类不同杀菌剂(代森新、代森锰锌、多菌灵)、热处理温度(40、45、50℃)、热处理时间(30、45、60min)和不
一台录音机的磁头磁化了,其简易的测试方法是:给录音机装入新磁带或刚抹音的磁带,将电流电压表连接在录音机输出端上,使输入控制置于“关”位置或使输入电路短路,放一分钟磁
近两年来,牡丹54C3A彩电出现随意关机的故障率较高,主要表现在等待电源指示灯亮,不能开机,且伴有较小的“噗噗”声;或能开机,但数分钟后又自动关机,这种故障出现后,有的彩电
ECI电讯公司宣布,由其研制的Hi-TV系统现在已具备支持基于ATM的IP应用功能。Hi-TV系统的这项新功能。(支持基于ATM的IP应用)专为满足广播和电视后期制作的紧迫需要而设计,该