On the equitable total chromatic number of cubic graphs

详细信息    查看全文

• 作者：S. Dantas^a ; ^{sdantas@im.uff.br" class="auth_mail" title="E-mail the corresponding author} ; C.M.H. de Figueiredo^b ; ^{celina@cos.ufrj.br" class="auth_mail" title="E-mail the corresponding author} ; G. Mazzuoccolo^c ; ^{mazzuoccolo@unimore.it" class="auth_mail" title="E-mail the corresponding author} ; M. Preissmann^d ; ^{Myriam.Preissmann@g-scop.inpg.fr" class="auth_mail" title="E-mail the corresponding author} ; V.F. dos Santos^e ; ^{viniciussantos@decom.cefetmg.br" class="auth_mail" title="E-mail the corresponding author} ; D. Sasaki^f ; ^{diana.sasakidesouzapereira@dauphine.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Cubic graphs ; Equitable total-coloring ; NP-complete
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 August 2016
• 年：2016
• 卷：209
• 期：Complete
• 页码：84-91
• 全文大小：568 K

文摘

A total coloring is equitable if the number of elements colored with each color differs by at most one, and the least integer for which a graph has such a coloring is called its equitable total chromatic number. Wang conjectured that the equitable total chromatic number of a multigraph of maximum degree class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005004&_mathId=si20.gif&_user=111111111&_pii=S0166218X15005004&_rdoc=1&_issn=0166218X&md5=75b1a6df9057295a00a452c24046002f" title="Click to view the MathML source">Δclass="mathContainer hidden">class="mathCode">$\Delta$ is at most class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005004&_mathId=si21.gif&_user=111111111&_pii=S0166218X15005004&_rdoc=1&_issn=0166218X&md5=0183c752251491a6346dc37de4a9eda1" title="Click to view the MathML source">Δ+2class="mathContainer hidden">class="mathCode">$\Delta +2$, and proved this for the case where class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X15005004&_mathId=si22.gif&_user=111111111&_pii=S0166218X15005004&_rdoc=1&_issn=0166218X&md5=e957ce66d10346c7c2e8d4ed10dc0211" title="Click to view the MathML source">Δ≤3class="mathContainer hidden">class="mathCode">$\Delta \le 3$. Therefore, the equitable total chromatic number of a cubic graph is either 4 or 5, and in this work we prove that the problem of deciding whether it is 4 is NP-complete for bipartite cubic graphs.

Furthermore, we present the first known Type 1 cubic graphs with equitable total chromatic number 5. All of them have, by construction, a small girth. We also find one infinite family of Type 1 cubic graphs of girth 5 having equitable total chromatic number 4. This motivates the following question: Does there exist Type 1 cubic graphs of girth greater than 5 and equitable total chromatic number 5?