Back to Search
Start Over
A Sufficient Condition for Planar Graphs of Maximum Degree 6 to be Totally 7-Colorable.
- Source :
-
Discrete Dynamics in Nature & Society . 4/11/2020, p1-8. 8p. - Publication Year :
- 2020
-
Abstract
- A total k -coloring of a graph is an assignment of k colors to its vertices and edges such that no two adjacent or incident elements receive the same color. The total coloring conjecture (TCC) states that every simple graph G has a total Δ G + 2 -coloring, where Δ G is the maximum degree of G. This conjecture has been confirmed for planar graphs with maximum degree at least 7 or at most 5, i.e., the only open case of TCC is that of maximum degree 6. It is known that every planar graph G of Δ G ≥ 9 or Δ G ∈ 7,8 with some restrictions has a total Δ G + 1 -coloring. In particular, in (Shen and Wang, 2009), the authors proved that every planar graph with maximum degree 6 and without 4-cycles has a total 7-coloring. In this paper, we improve this result by showing that every diamond-free and house-free planar graph of maximum degree 6 is totally 7-colorable if every 6-vertex is not incident with two adjacent four cycles or three cycles of size p , q , ℓ for some p , q , ℓ ∈ 3,4,4 , 3,3,4 . [ABSTRACT FROM AUTHOR]
- Subjects :
- *PLANAR graphs
*LOGICAL prediction
Subjects
Details
- Language :
- English
- ISSN :
- 10260226
- Database :
- Academic Search Index
- Journal :
- Discrete Dynamics in Nature & Society
- Publication Type :
- Academic Journal
- Accession number :
- 142684842
- Full Text :
- https://doi.org/10.1155/2020/3196540