Total coloring of 1-toroidal graphs with maximum degree at least 11 and no adjacent triangles

Tao Wang ()
Additional contact information
Tao Wang: Henan University

Journal of Combinatorial Optimization, 2017, vol. 33, issue 3, No 17, 1090-1105

Abstract: Abstract A total coloring of a graph G is an assignment of colors to the vertices and the edges of G such that every pair of adjacent/incident elements receive distinct colors. The total chromatic number of a graph G, denoted by $$\chi ''(G)$$ χ ′ ′ ( G ) , is the minimum number of colors in a total coloring of G. The well-known total coloring conjecture (TCC) says that every graph with maximum degree $$\Delta $$ Δ admits a total coloring with at most $$\Delta + 2$$ Δ + 2 colors. A graph is 1-toroidal if it can be drawn in torus such that every edge crosses at most one other edge. In this paper, we investigate the total coloring of 1-toroidal graphs, and prove that the TCC holds for the 1-toroidal graphs with maximum degree at least 11 and some restrictions on the triangles. Consequently, if G is a 1-toroidal graph with maximum degree $$\Delta $$ Δ at least 11 and without adjacent triangles, then G admits a total coloring with at most $$\Delta + 2$$ Δ + 2 colors.

Keywords: Total coloring; 1-Toroidal graph; 1-Planar graph; Total coloring conjecture (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-016-0025-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:3:d:10.1007_s10878-016-0025-9

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-016-0025-9

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().