On total colorings of some special 1-planar graphs (Q2401770): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Jian Liang Wu / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Shriram K. Nimbhorkar / rank | |||
Normal rank |
Revision as of 21:09, 19 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On total colorings of some special 1-planar graphs |
scientific article |
Statements
On total colorings of some special 1-planar graphs (English)
0 references
5 September 2017
0 references
The total coloring conjecture says that every simple graph of maximum degree \(\Delta\) admits a total \((\Delta+2)\)-coloring. In this paper, the authors prove this conjecture for a certain class of graphs. A graph is 1-planar if it can be drawn on the plane so that each edge is crossed by at most one other edge. The total chromatic number \(\chi^{\prime\prime}(G)\) of a graph \(G\) is the least number of colors needed in any total coloring of \(G\). If \(G\) has a total \(k\)-coloring, then \(G\) is called totally \(k\)-colorable. The following theorems are proved. Let \(G\) be a 1-planar graph with maximum degree \(\Delta\) and \(g(G) \geq 4\), and let \(r\) be a positive integer. If \(\Delta \leq r\) and \(r \geq 9\), then \(\chi^{\prime\prime}\leq r + 2\). Let \(G\) be a 1-planar graph with maximum degree \(\Delta\) and \(g(G) \geq 5\), and let \(r\) be a positive integer. If \(\Delta \leq r\) and \(r \geq 7\), then \(\chi^{\prime\prime}\leq r + 2\).
0 references
1-planar graph
0 references
total coloring
0 references
discharging method
0 references
girth
0 references
\(r\)-minimal graph
0 references