Improved edge-coloring algorithms for planar graphs

Appel, 1976, Every planar map is four colorable, Bull. Amer. Math. Soc., 82, 711, 10.1090/S0002-9904-1976-14122-5 Berge, 1973 Boyar, 1987, Coloring planar graphs in parallel, J. Algorithms, 8, 470, 10.1016/0196-6774(87)90046-0 Chiba, 1981, A linear algorithm for five-coloring a planar graph, J. Algorithms, 2, 317, 10.1016/0196-6774(81)90031-6 Chrobak, 1989, Fast algorithms for edge-coloring planar graphs, J. Algorithms, 10, 35, 10.1016/0196-6774(89)90022-9 Cole, 1982, On edge coloring bipartite graphs, SIAM J. Comput., 11, 540, 10.1137/0211043 Cole, 1986, Deterministic coin tossing and accelerating cascades: Micro and marco techniques for designing parallel algorithms, 206 Frederickson, 1984, On linear-time algorithms for five-coloring planar graphs, Inform. Process. Lett., 19, 219, 10.1016/0020-0190(84)90056-5 Fiorini, 1977 Garey, 1976, Some simplified NP-complete problems, Theoret. Comput. Sci., 1, 237, 10.1016/0304-3975(76)90059-1 Gabow, 1982, Algorithms for edge coloring bipartite graphs and multigraphs, SIAM J. Comput., 11, 117, 10.1137/0211009 Gabow, 1985 Goldberg, 1987, Parallel symmetry breaking in sparse graphs Hagerup, 1989, Optimal parallel 5-colouring of planar graphs, 18, 288 Hochbaum, 1986, A better than “best possible” algorithm to edge color multigraphs, J. Algorithms, 7, 79, 10.1016/0196-6774(86)90039-8 Holyer, 1981, The NP-completeness of edge coloring, SIAM J. Comput., 10, 718, 10.1137/0210055 Holyer, 1980, The Computational Complexity of Graph Theory Problems Karloff, 1987, Efficient parallel algorithms for edge coloring problems, J. Algorithms, 8, 39, 10.1016/0196-6774(87)90026-5 Luby, 1986, A simple parallel algorithm for the maximal independent set problem, 15, 1036 Leven, 1983, NP-completeness of finding the chromatic index of regular graphs, J. Algorithms, 4, 35, 10.1016/0196-6774(83)90032-9 Lev, 1981, A fast parallel algorithm for routing in permutation networks, IEEE Trans. Comput., C-30, 93, 10.1109/TC.1981.6312171 D. Matula, Y. Shiloah, and R. Tarjan, “Two linear-time algorithms for five-coloring a planar graph,” Tech. Rep. No. STAN-CS-80-830, Department of Computer Science, Stanford University. Naor, 1987, A fast parallel coloring of planar graphs with five colors, Inform. Process. Lett., 25, 51, 10.1016/0020-0190(87)90092-5 Shannon, 1949, A theorem on colouring lines of a network, J. Math. Phys., 28, 148, 10.1002/sapm1949281148 Vizing, 1964, On the estimate of the chromatic class of a p-graph, Discret. Anal., 3, 25 Vizing, 1965, Critical graphs with a given chromatic number, Diskret. Anal., 5, 9 Williams, 1985, A linear algorithm for coloring planar graphs with five colors, Comput. J., 28, 78, 10.1093/comjnl/28.1.78