Acyclic edge coloring conjecture is true on planar graphs without intersecting triangles

被引:3
作者
Shu, Qiaojun [1 ,3 ]
Chen, Yong [1 ]
Han, Shuguang [2 ,3 ]
Lin, Guohui [3 ]
Miyano, Eiji [4 ]
Zhang, An [1 ,3 ]
机构
[1] Hangzhou Dianzi Univ, Dept Math, Hangzhou, Peoples R China
[2] Zhejiang Sci Tech Univ, Dept Math, Hangzhou, Peoples R China
[3] Univ Alberta, Dept Comp Sci, Edmonton, AB T6G 2E8, Canada
[4] Kyushu Inst Technol, Dept Artificial Intelligence, Iizuka, Fukuoka, Japan
关键词
Acyclic edge coloring; Planar graph; Intersecting triangles; Discharging; Induction; CHROMATIC INDEXES; 4-REGULAR GRAPHS;
D O I
10.1016/j.tcs.2021.06.017
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic edge coloring conjecture by Fiamcik (1978) and Alon, Sudakov and Zaks (2001) states that every simple graph with maximum degree Delta is acyclically edge (Delta + 2)-colorable. Despite many milestones, the conjecture remains open even for planar graphs. In this paper, we confirm affirmatively the conjecture on planar graphs without intersecting triangles. We do so by first showing, by discharging methods, that every planar graph without intersecting triangles must have at least one of the six specified groups of local structures, and then proving the conjecture by recoloring certain edges in each such local structure and by induction on the number of edges in the graph. (C) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页码:77 / 108
页数:32
相关论文
共 24 条
[1]   Acyclic edge colorings of graphs [J].
Alon, N ;
Sudakov, B ;
Zaks, A .
JOURNAL OF GRAPH THEORY, 2001, 37 (03) :157-167
[2]   ACYCLIC COLORING OF GRAPHS [J].
ALON, N ;
MCDIARMID, C ;
REED, B .
RANDOM STRUCTURES & ALGORITHMS, 1991, 2 (03) :277-288
[3]   Optimal acyclic edge-coloring of cubic graphs [J].
Andersen, Lars Dovling ;
Macajova, Edita ;
Mazak, Jan .
JOURNAL OF GRAPH THEORY, 2012, 71 (04) :353-364
[4]   ACYCLIC EDGE-COLORING OF PLANAR GRAPHS [J].
Basavaraju, Manu ;
Chandran, L. Sunil ;
Cohen, Nathann ;
Havet, Frederic ;
Mueller, Tobias .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2011, 25 (02) :463-478
[5]   Acyclic Edge Coloring of Graphs with Maximum Degree 4 [J].
Basavaraju, Manu ;
Chandran, L. Sunill .
JOURNAL OF GRAPH THEORY, 2009, 61 (03) :192-209
[6]   Acyclic edge-coloring using entropy compression [J].
Esperet, Louis ;
Parreau, Aline .
EUROPEAN JOURNAL OF COMBINATORICS, 2013, 34 (06) :1019-1027
[7]  
Fiamcik J., 1978, Math Slovaca, V28, P139
[8]   Acyclic edge coloring through the Lovasz Local Lemma [J].
Giotis, Ioannis ;
Kirousis, Lefteris ;
Psaromiligkos, Kostas I. ;
Thilikos, Dimitrios M. .
THEORETICAL COMPUTER SCIENCE, 2017, 665 :40-50
[9]   Acyclic chromatic index of planar graphs with triangles [J].
Hou, Jianfeng ;
Roussel, Nicolas ;
Wu, Jianliang .
INFORMATION PROCESSING LETTERS, 2011, 111 (17) :836-840
[10]  
Kirousis L., 2020, ARXIV190107856V6MATH ARXIV190107856V6MATH