Equitable total coloring of Kn ödel graph WΔ,n

被引：0

作者：

Tong, Chunling ^{[1
]}

Dong, Aijun ^{[2
]}

Wang, Shouqiang ^{[1
]}

Yang, Yuansheng ^{[3
]}

机构：

[1] College of Information Science and Electricity Engineering, Shandong Jiaotong University, Ji'nan

[2] College of Science, Shandong Jiaotong University, Ji'nan

[3] College of Computer Science, Dalian University of Technology, Dalian

来源：

Journal of Computational Information Systems | 2014年 / 10卷 / 22期

基金：

中国国家自然科学基金;

关键词：

chromatic number; Equitable total; Equitable total coloring; Knödel graph; Total chromatic number; Total coloring;

D O I：

10.12733/jcis13126

中图分类号：

学科分类号：

摘要：

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ö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ö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. Copyright © 2014 Binary Information Press.

引用

页码：9821 / 9829

页数：8

共 20 条

[1]

S'anchez-Arroyo A., Determining the total coloring number is NP-hard, Discrete Mathematics, 78, pp. 315-319, (1989)

[2]

McDiarmid C.J.H., S'anchez-Arroyo A., Total coloring regular bipartite graphs is NP-hard, Discrete Mathematics, 124, pp. 155-162, (1994)

[3]

Behzad M., Graphs and their chromatic numbers, (1965)

[4]

Some unsolved problems in graph theory, Uspehi Matematicheskih Nauk, 23, pp. 117-134, (1968)

[5]

Wang B., Wu J.L., Total colorings of planar graphs without intersecting 5-cycles, Discrete Applied Mathematics, 160, pp. 1815-1821, (2012)

[6]

Xu R.Y., Wu J.L., Total coloring of planar graphs with 7-cycles containing at most two chords, Theoretical Computer Science, 520, pp. 124-129, (2014)

[7]

Leidner M., A Larger Family of Planar Graphs that Satisfy the Total Coloring Conjecture, Graph Combinatorics, 30, 2, pp. 377-388, (2014)

[8]

Khennoufa R., Togni O., Total and fractional total colorings of circulant graphs, Discrete Applied Mathematics, 308, pp. 6316-6329, (2008)

[9]

Campos C.N., Dantas S., De Mello C.P., The total-chromatic number of some families of snarks, Discrete Mathematics, 311, pp. 984-988, (2011)

[10]

Fu H.L., Some results on equalized total coloring, Congressus Numerantium, 102, pp. 111-119, (1994)

← 1 2 →