Total coloring of recursive maximal planar graphs

被引：3
作者：
Zhou, Yangyang [1 ]
Zhao, Dongyang [1 ]
Ma, Mingyuan [1 ]
Xu, Jin [1 ]
机构：
[1] Peking Univ, Sch Elect Engn & Comp Sci, Beijing, Peoples R China
来源：
THEORETICAL COMPUTER SCIENCE | 2022年 / 909卷
基金：
中国国家自然科学基金; 国家重点研发计划;
关键词：
Total coloring; Total chromatic number; Recursive maximal planar graph; (2,2)-recursive maximal planar graph; Total coloring algorithm; TOTAL CHROMATIC NUMBER;
D O I：
10.1016/j.tcs.2022.01.024
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The recursive maximal planar graphs can be obtained from K-4, by embedding a 3-vertex in a triangular face continuously. A total k-coloring of a graph G is a coloring of its vertices and edges such that no two adjacent or incident elements receive the same color. The Total Coloring Conjecture, in short, TCC, states that every simple graph G is totally (Delta + 2)-colorable, where Delta is the maximum degree of G. In this paper, we prove that TCC holds for recursive maximal planar graphs, especially, a main class of recursive maximal planar graphs, named (2,2)-recursive maximal planar graphs, are totally (Delta + 1)-colorable. Moreover, we give linear time algorithms for total coloring of recursive maximal planar graphs and (2,2)-recursive maximal planar graphs, respectively. (C) 2022 Elsevier B.V. All rights reserved.
引用
收藏
页码：12 / 18
页数：7
相关论文
共 16 条
12