From L. Euler to D. König
RAIRO - Operations Research - Recherche Opérationnelle, Volume 43 (2009) no. 3, p. 247-251

Starting from the famous Königsberg bridge problem which Euler described in 1736, we intend to show that some results obtained 180 years later by König are very close to Euler's discoveries.

DOI : https://doi.org/10.1051/ro/2009020
Classification:  05C15
Keywords: eulerian graph, edge coloring, parity, König theorem
@article{RO_2009__43_3_247_0,
     author = {Werra, Dominique de},
     title = {From L. Euler to D. K\"onig},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {3},
     year = {2009},
     pages = {247-251},
     doi = {10.1051/ro/2009020},
     zbl = {1175.05003},
     mrnumber = {2567987},
     language = {en},
     url = {http://www.numdam.org/item/RO_2009__43_3_247_0}
}
Werra, Dominique de. From L. Euler to D. König. RAIRO - Operations Research - Recherche Opérationnelle, Volume 43 (2009) no. 3, pp. 247-251. doi : 10.1051/ro/2009020. http://www.numdam.org/item/RO_2009__43_3_247_0/

[1] C. Berge, Graphes. Gauthier-Villars, Paris (1983). | MR 722294 | Zbl 0531.05031

[2] D. De Werra, Equitable colorations of graphs. Revue Française d'Informatique et de Recherche Opérationnelle R-3 (1971) 3-8. | Numdam | MR 543812 | Zbl 0239.05112

[3] L. Euler, Solutio problematis ad geometriam situs pertinentis, Commentarii Academiae Scientiarum Imperialis Petropolitanae 8 (1736) 128-140. Reprinted in: Leonhardi Euleri - Opera Omnia - Series Prima - Opera Mathematica - Commentationes Algebraicae, L.G. du Pasquier Ed., Teubner, Leipzig (1923) 1-10.

[4] H.N. Gabow, Using Euler partitions to edge color bipartite multigraphs. Int. J. Parallel Prog. 5 (1976) 345-355. | MR 422081 | Zbl 0411.05039

[5] I. Gribkovskai, Ø. Halskan and G. Laporte, The bridges of Königsberg - a historical perspective. Networks 49 (2007) 199-203. | MR 2307410 | Zbl 1151.01007

[6] C. Hierholzer, Über die Möglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren. Math. Ann. 6 (1873) 30-32. | JFM 05.0286.02 | MR 1509807

[7] D. König, Graphok és alkalmazásuk a determinánsok és a halmazok elméletére (Hungarian). Mathematikai és Természettudományi Értesitö 34 (1916) 104-119. | JFM 46.1451.03

[8] A. Schrijver, Bipartite edge coloring in 0(δm)time. SIAM J. Comput. 28 (1998) 841-846. | MR 1643453 | Zbl 0918.68071