Randomized Δ-edge colouring via exchanges of complex colours

References

• Aggarwal , G. , Motwani , R. , Shah , D. and Zhu , A. 2003 . Switch scheduling via randomized edge coloring . Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science , p. 502.
   Google Scholar
• D. Aldous and J. Fill, Reversible Markov Chains and Random Walks on Graphs (monograph in preparation), 2002. Available at http://stat-www.berkeley.edu/users/aldous/RWG/book.html.
   Google Scholar
• Aleliunas , R. , Karp , R. , Lipton , R. , Lovász , L. and Rackoff , C. 1979 . Random walks, universal travelling, sequences, and the complexity of maze problems . Proceeding of 20th Annual Symposium on Foundations of Computer Science , : 218 – 223 .
   Google Scholar
• Appel , K. and Haken , W. 1989 . Every Planar Map is Four Colorable . American Mathematical Society, Providence , RI
   Google Scholar
• Beigel , R. and Eppstein , D. 1995 . 3-coloring in time O(1.3446 n ): A no-MIS algorithm . 36th IEEE Symposium on Foundations of Computer Science , p. 444.
   Google Scholar
• Cole , R. , Ost , K. and Schirra , S. 2001 . Edge-coloring bipartite multigraphs in O (E log D) time . Combinatorica , 21 : 5 – 12 . (doi:10.1007/s004930170002)
   Web of Science ®Google Scholar
• Conway , J. and Smith , D. 2003 . On Quaternions and Octonions , Natick , MA : AK Peters .
   Google Scholar
• Dubhashi , D. , Grable , D. and Panconesi , A. 1998 . Near-optimal, distributed edge colouring via the nibble method . Theoret. Comput. Sci. , 203 : 225 – 251 . (doi:10.1016/S0304-3975(98)00022-X)
   Web of Science ®Google Scholar
• Edmonds , J. 1987 . “ Paths, trees, and flowers ” . In Classic Papers in Combinatorics , Edited by: Gessel , I. and Rota , G.-C. 361 – 379 . Boston : Birkhäuser .
   Google Scholar
• Eppstein , D. 2001 . Improved algorithms for 3-coloring, 3-edge-coloring, and constraint satisfaction . Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms , : 329 – 337 .
   Google Scholar
• Fronczak , A. , Fronczak , P. and Hołyst , J. 2004 . Average path length in random networks . Phys. Rev. E , 70 ( 5 ) Article ID 056110. Available at http://pre.aps.org/abstract/PRE/v70/i5/e056110. (doi:10.1103/PhysRevE.70.056110)
   Web of Science ®Google Scholar
• Gabow , H. , Nishizeki , T. , Kariv , O. , Leven , D. and Terada , O. 1985 . Algorithms for edge-coloring graphs . Tech. Rep. ,
   Google Scholar
• Grable , D. and Panconesi , A. 1997 . Nearly optimal distributed edge colouring in O (log log n) rounds . Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , : 278 – 285 .
   Google Scholar
• Hilgemeier , M. , Drechsler , N. and Drechsler , R. 2003 . Fast heuristics for the edge coloring of large graphs . Proceedings of the Euromicro Symposium on Digital System Design , : 230 – 237 . (doi:10.1109/DSD.2003.1231932)
   Google Scholar
• Holyer , I. 1981 . The NP-completeness of edge-colouring . SIAM J. Comput. , 10 : 718 – 720 . (doi:10.1137/0210055)
   Web of Science ®Google Scholar
• Kempe , A. 1879 . On the geographical problem of the four colours . Am. J. Math. , 2 : 193 – 200 . (doi:10.2307/2369235)
   Google Scholar
• Lovász , L. 1993 . “ Random walks on graphs: A survey ” . In Combinatorics, Paul Erdős is Eighty , Edited by: Miklós , D. , Sós , V. T. and Szőnyi , T. Vol. 2 , 1 – 46 . Hungary : Budapest . János Bolyai Mathematical Society
   Google Scholar
• Robertson , N. , Sanders , D. , Seymour , P. and Thomas , R. 1997 . The four-colour theorem . J. Combin. Theory Ser. B , 70 : 2 – 44 . (doi:10.1006/jctb.1997.1750)
   Web of Science ®Google Scholar
• Steger , A. and Wormald , N. 1999 . Generating random regular graphs quickly . Combin. Probab. Comput. , 8 : 377 – 396 . (doi:10.1017/S0963548399003867)
   Web of Science ®Google Scholar
• Tait , P. 1880 . Note on a theorem in geometry of position . Trans. R. Soc. Edinburgh , 29 : 657 – 660 .
   Google Scholar
• West , D. 2001 . Introduction to Graph Theory , Upper Saddle River , NJ : Prentice Hall .
   Google Scholar