No Detail Found!

A brief history of edge-colorings - with personal reminiscences

Author(s)
Bjarne Toft Department of Mathematics and Computer Science, University of Southern Denmark, Odense, Denmark
Robin Wilson Department of Mathematics and Statistics, Open University, Walton Hall, Milton Keynes, UK; Department of Mathematics, London School of Economics and Political Science, London, UK
Abstract
In this article we survey some important milestones in the history of edge-colorings of graphs, from the earliest contributions of Peter Guthrie Tait and De´nes Ko¨nig to very recent work.
Publication Details
Page(s) 38-46
Published Journal: Discrete Mathematics Letters, Volume: 6, Issue: 0, Year: 2021

Request the full text from PASTIC

Keywords
edge-coloring, Frank Harary, graph theory history
References
Andersen L. D.,Non-Simple Graphs M.,Sc M. .1977 .On edge-colourings of graphs. Mat. Scand, 40 : 161-175.
Andersen L. D.,S. Fiorini, L. D. . .Note on the non-existence of certain non-3-edge-colorable graphs, Unpublished preprint. , : .
Asplund J.,J. McDonald J. .2016 .On a limit of the method of Tashkinov trees for edge-coloring. , 339 : 2231-2238.
Behzad M. .1965 .. Graphs and their Chromatic Numbers, Ph.D. thesis, : .
Beineke L. W.,Fiorini S. .1976 .On small graphs critical with respect to edge-colourings. , 16 : 109-121.
Beineke L. W. .1973 .On the edge-chromatic number of a graph. Discrete Math. 5, : 15-20.
Bollob B.,Harris B. .1985 .List-colourings of graphs. Graphs Combin, 1 : 115-127.
Chen G. .1901 .Proof of the Goldberg-Seymour Conjecture on edge-colorings of multigraphs. , : .
Chetwynd A. G.,Hilton A. J. W.,D. Andersen I. T.,Jakobsen P.,Vestergaard B.,Toft C. .1989 .The edge-chromatic class of graphs with maximum degree at least jV j 3. Graph Theory in Memory of G. A. Dirac (Annals of Discrete Mathematics 41), : 91-110.
Chetwynd A. G. .1981 .Snarks and supersnarks. Theory and Applications of Graphs (Fourth Int. Conference, : 215-241.
Erdo P. .1977 .On the chromatic index of almost all graphs. J. Combin. Theory Ser. B, 23 : 255-257.
Favrholdt L. M.,Stiebitz M.,Toft B.,IMADA-PP-2006- B. . .Graph edge colouring: Vizing's theorem and Goldberg's conjecture. -10-003, : 20.
Fiorini S. .1978 .A bibliographic survey of edge-colorings. J. Graph Theory, 2 : 93-106.
Fiorini S. .1977 .. , : .
Gru S.,Sanders D. P.,Zhao Y. .2001 .Planar graphs of maximum degree seven are class I, J. Theory Ser. B, 83 : 201-212.
Gupta R. P.,Alavi D. R.,Lick D. R. .1978 .On the chromatic index and cover index of a multigraph. Theory and Applications of Graphs (Lecture Notes in Mathematics 642), : 204-215.
Gupta R. P. .1967 .Studies in the Theory of Graphs. Ph.D. thesis, : .
Galvin F. .1995 .The list chromatic index of a bipartite multigraph. J. Combin. Theory Ser. B, 63 : 153-158.
M. K. Goldberg .1973 .3-7; A detailed discussion can be found in Ref. Diskret. Analiz, 38 : .
M. K. Goldberg ,Ser J. Combin. Theory .1981 .Construction of class two graphs with maximum vertex degree 3. B, 31 : 282-291.
M. K. Goldberg .1984 .Edge-coloring of multigraphs: recoloring technique. J. Graph Theory, 8 : 123-137.
Harary F.,Addison-Wesley F. .1969 .. , : .
I. Holyer .1980 .The NP-completeness of edge-coloring. SIAM J. Comput, 10 : 718-720.
Jakobsen I. T. .1974 .On critical graphs with chromatic index 4. , 9 : 265-276.
Jensen T. R.,Toft B. .1995 .. , : .
Jensen T. R.,Toft B. .2015 .Unsolved graph coloring problems. Topics in Chromatic Graph Theory, : 327-357.
A. B. Kempe .1879 .see also Chapter 6 of the book mentioned in Ref. Amer. J. Math. 2, 32 : 193-200.
Kierstead H. .1984 .On the chromatic index of multigraphs without large triangles. J. Combin. Theory Ser. B, 36 : 156-160.
Ko D. .1916 .an English translation appears in the book mentioned in Ref. , 32 : 104-119.
J. McDonald .2015 .Edge-colourings. Topics in Chromatic Graph Theory, : 94-113.
Nishizeki T.,Kashiwagi K. .1990 .On the 1.1-edge-coloring of multigraphs. Siam J. Discrete Math. 3, : 391-410.
Petersen J.,Biggs E. K.,Lloyd E. K. .1976 .see also Chapter 10 of the book. Graph Theory 1736-1936, 5 : 225-227.
Reed B.,Seymour P. .2004 .Hadwiger's conjecture for line graphs. European J. Combin, 25 : 873-875.
Scheide D. .2010 .Graph edge colouring: Tashkinov trees and Goldberg's conjecture. J. Combin. Theory Ser. B, 100 : 68-96.
Seymour P. D. .1979 .On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. London Math. Soc, 38 : 423-460.
Seymour P. D.,Bondy U. S. R.,Murty U. S. R. .1979 .Some unsolved problems on one-factorizations of graphs. Graph Theory and Related Topics (Proc. Conf, : 367-368.
Shannon C. E. .1949 .A theorem on coloring the lines of a network. J. Math. Phys. 28, : 148-151.
Stiebitz M.,Scheide D.,Toft B.,Favrholdt L. M. .2012 .Vizing's Theorem and Goldberg's Conjecture. , : .
P. G. Tait, .1880 .Remarks on the colouring of maps. Proc. Roy. Soc. Edinburgh, 29 : 501-503.
Tashkinov V. .2000 .On an algorithm for the edge coloring of multigraphs (Russian), Diskretn. Anal. Issled. Oper. (Ser. 1), (7) : 72-85.
Vizing V. G. .1964 .an English translation appears in Ref. Diskret. Analiz, 38 : 269-272.
V. G. Vizing, .1965 .an English translation appears in Ref. Diskret. Analiz, 38(Cybernetics 1) : 273-278.
V. G. Vizing, .1968 .Some unsolved problems in graph theory (Russian). Russian Math. Surveys, 23 : 125-141.
Whitney H.,Brooks H. .1941 .On colouring the nodes of a network. Proc. Cambridge Philos. Soc, 37 : 194-197.
R. J .2010 .. , : .
Yan C.,Stiebitz M.,Toft B. .2019 .Graph edge coloring: a survey. Graphs Combin, 35 : 33-66.
0

Citations

0

Downloads

13

Views