New Linear-Time Algorithms for Edge-Coloring Planar Graphs

New Linear-Time Algorithms for Edge-Coloring Planar Graphs Richard Cole Lukasz Kowalik y Abstract We show e cient algorithms for edge-coloring planar graphs. Our main result is a linear-time algorithm for coloring planar graphs with maximum degree with maxf ;9g colors. Thus the coloring is opti- mal for graphs with maximum degree 9. Moreover for = 4;5;6 we give linear-time algorithms that use + 2 colors. These results improve over the algorithms of Chrobak and Yung [1] and of Chrobak and

Nishizeki [2] which color planar graphs using maxf ;19g colors in linear time or using maxf ;9g colors in O(nlogn) time. Keywords. Edge-coloring, linear-time, algorithm, planar graph 1 Introduction In the problem of edge-coloring the input is an undirected graph and the task is to assign colors to the edges so that edges with a common endpoint have di erent colors. This is one of the most natural graph coloring problems and arises in a variety of scheduling applications. Throughout the paper (G) will denote the maximum degree in graph G; we write for short when there is no ambiguity. Trivially at least colors are needed to color the edges of any graph. Vizing [3] proved that + 1 colors always su ce. Unfortunately it is NP-complete even for cubic graphs to decide whether a Computer Science Department, New York University, 251 Mercer Street, New York, NY 10012, USA. cole@cs.nyu.edu. Supported in part by NSF grants CCR0105678 and CCF0515127. yInstitute of Informatics, Warsaw University, Banacha 2, 02-097, Warsaw, Poland and Max-Planck-Institute f ur Informatik, Stuhlsatzenhausweg 85, 66123 Saarbr ucken, Ger- many. E-mail: kowalik@mimuw.edu.pl, phone: +49 681 9325 118, fax: +49 681 9325 199. Supported in part by KBN grant 4T11C04425....

Website: www.cs.nyu.edu | Filesize: -
No of Page(s): 23
Download New Linear-Time Algorithms for Edge-Coloring Planar Graphs.pdf