حدس های زیبا در نظریه گراف

نوع مقاله: مقاله ترجمه ای

نویسندگان

1 دانشگاه یزد

2 دانشگاه تربیت مدرس تهران

چکیده

به طور قطع، هر آنچه که در ریاضیات مطرح می‌شود الزاماً زیبا نیست. اما با باور به این‏‌که زیبایی در بطن بهترین‌ قسمت‌های ریاضی قرار دارد، تلاش می‌کنیم تا برخی از بهترین حدس‌های مربوط به نظریه‌ی گراف را گردآوری کنیم که با ملاک‌های مختلف زیبایی جور در بیایند.

کلیدواژه‌ها

موضوعات


[1] M. Aigner and G. Ziegler, Proofs from the Book, Including illustrations by Karl H. Hofmann. Third edition. Springer-Verlag, Berlin, 2004.

[1] P. J. Kelly, On Isometric Transformations, Ph. D. thesis, University of Wisconsin, 1942.

[2] S. M. Ulam, A Collection of Mathematical Problems, Wiley (Interscience), New York, 1960 pp. 29.

[3] F. Harary, On the reconstruction of a graph from a collection of subgraphs, Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963, ed. M. Fiedler.), Publ. House Czechoslovak Acad. Sci., Prague, 1964, 47–52; reprinted by Academic Press, New York.

[4] C. Thomassen, Counterexamples to the Edge Reconstruction Conjecture for infinite graphs, Discrete Math., 19 (1977) 293–295.

[5] R. P. Stanley, Reconstruction from vertex-switching, J. Combin. Theory Ser. B., 38 (1985) 132–138.

[6] M. N. Ellingham, Recent progress in edge reconstruction, Congressus Numerantium, 62 (1988) 3–20.

[7] J. A. Bondy, A graph reconstructor’s manual, in Surveys in Combinatorics. Proc. 13th. British Combinatorial Conf., London Math. Soc. Lecture Notes Series 166 (ed. A. D. Keedwell), Cambridge University Press, Cambridge, 1991.

[8] L. Babai, Automorphism groups, isomorphism, reconstruction. Chapter 27 of the Handbook of Combinatorics (R. L. Graham, M. Grِtschel and L. Lovsz, eds.), North-Holland–Elsevier, 1995 1447–1540.

[9] J. Lauri and R. Scapellato, Topics in Graph Automorphisms and Reconstruction, London Math. Soc. Student Texts, 54 Cam-bridge University Press, 2003.

[1] L. Lovász, On covering of graphs, in Theory of Graphs (P. Erdős and G. Katona and eds.), Academic Press, New York, 1968, 231–236.

[2] J. W. Moon, Topics on Tournaments, Holt, Rinehart and Winston, New York, 1968, pp. 7.

[3] A. Donald, An upper bound for the path number of a graph, J. Graph Theory, 4 (1980) 189–201.

[4] T. Jiang, Hajós conjecture is true for planar graphs, J. China Univ. Sci. Tech., 14 (1984) 585–592.

[5] O. Favaron and M. Kouider, Path partitions and cycle partitions of eulerian graphs of maximum degree 4, Studia Sci. Math. Hungarica, 23 (1988) 237–244.

[1] J. Edmonds, Maximum matching and a polyhedron with (0,1) vertices, J. Res. Nat. Bur. Standards Ser. B., 8 (1965) 125–130.

[2] D. R. Fulkerson, Blocking and antiblocking pairs of polyhedra, Math. Programming, 1 (1971) 168–194.

[3] G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Austral. Math. Soc., 8 (1973) 367–387.

[4] P. D. Seymour, Sums of circuits, in Graph Theory and Related Topics (J. A. Bondy, U. S. R. Murty and eds.), Academic Press, New York, 1979 341–355.

[5] M. Preissmann, Sur les colorations des arêtes des graphes cubiques, Thèse de doctorat de 3ème cycle, Université de Grenoble, 1981.

[6] J. C. Bermond, B. Jackson and F. Jaeger, Shortest coverings of graphs with cycles, J. Combin. Theory Ser. B., 35 (1983) 297–308.

[7] D. Archdeacon, Face colorings of embedded graphs, J. Graph Theory, 8 (1984) 387–398.

[8] F. Jaeger, A survey of the cycle double cover conjecture, in Cycles in Graphs (B. R. Alspach and C. D. Godsil and eds.), Ann. Discrete Math., 27, North-Holland, Amsterdam, 1985 1–12.

[9] J. A. Bondy, Small cycle double covers of graphs, in Cycles and Rays (G. Hahn, G. Sabidussi, R. Woodrow and eds.), NATO ASI Ser. C, Kluwer Academic Publishers, Dordrecht, 1990 21–40.

[10] H. Li, Perfect path double covers in every simple graph, J. Graph Theory, 14 (1990) 645–650.

[11] G. Fan, Integer flows and cycle covers, J. Combin. Theory Ser. B., 54 (1992) 113–122.

[12] C. Q. Zhang, Integer Flows and Cycle Covers of Graphs, Marcel Dekker, New York, 1997.

[1] W. T. Tutte, A contribution to the theory of chromatic polynomials, Canadian J. Math., 6 (1954) 80–91.

[2] P. D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B., 30 (1979) 130–135.

[3] F. Jaeger, Nowhere-zero flow problems, in Selected Topics in Graph Theory, L. W. Beineke, R. J. Wilson and eds., Academic Press, 1988 71–95.

[4] P. D. Seymour, Nowhere-zero flows, in Handbook of Combinatorics, (R. L. Graham, M. Grötschel, L. Lovász and eds.), North-Holland, 1995 289–299.

[5] C. Q. Zhang, Integer Flows and Cycle Covers of Graphs, Marcel Dekker, New York, 1997.

[1] H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljschr. Naturforsch. Gesellsch. Zürich, 88 (1943) 133–142.

[2] S. Hedetniemi, Homomorphisms of graphs and automata, Technical Report 03105-44-T, University of Michigan, 1966.

[3] R. L. Graham and H. O. Pollak, On the addressing problem for loop switching, Bell System Tech. J., 50 (1971) 2495–2519.

[4] K. Appel and W. Haken, A solution of the four-color map problem, Sci. Amer., 237 (1977) 108–121.

[5] H. Tverberg, On the decomposition of Kn into complete bipartite graphs, J. Graph Theory, 6 (1982) 493–494.

[6] M. El-Zahar and N. Sauer, The chromatic number of the product of two 4 -chromatic graphs is 4, Combinatorica, 5 (1985) 121–126.

[7] N. Robertson, P. Seymour and R. Thomas, Hadwiger’s conjecture for K6 -free graphs, Combinatorica, 13 (1993) 279–361.

[8] T. R. Jensen and B. Toft, Graph Coloring Problems, Wiley Interscience, 1995.

[9] B. Toft, A survey of Hadwiger’s Conjecture, in Surveys in Graph Theory (G. Chartrand and M. S. Jacobson,eds.), Congressus Numerantium, 115 (1996) 249–283.

[10] X. Zhu, A survey on Hedetniemi’s conjecture, Taiwanese J. Math., 12 (1998), 1–24.

[11] N. Sauer, Hedetniemi’s conjecture — a survey, Discrete Math., 229 (2001), 261–292.

[12] A. Thomason, The extremal function for complete minors, J. Combin. Theory Ser. B., 81 (2001) 318–338.

[13] D. Romero and A. Sánchez-Arroyo, Advances on the Erdős–Faber–Lovász Conjecture, this volume.

[1] B. Bollobás and A. J. Harris, List colourings of graphs, Graphs Combin., 1 (1985) 115–127.

[2] F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory Ser. B., 63 (1995) 153–158.

[3] J. Kahn, Asymptotically good list-colorings, J. Combin. Theory Ser. A., 73 (1996) 1–59.

[1] M. Behzad, Graphs and their Chromatic Numbers, Ph. D. thesis, Michigan State University, 1965.

[2] V. G. Vizing, Some unsolved problems in graph theory, Russian Math. Surveys, 23 (1968) 125–141.

[3] M. Molloy and B. Reed, A bound on the total chromatic number, Combinatorica, 18 (1998) 241–280.

[1] A. Adám, Problem 2, in Theory of Graphs and its Applications (M. Fiedler, ed.), Czech. Acad. Sci. Publ.,1964 pp.157.

[2] M. Behzad, G. Chartrand and C. E. Wall, On minimal regular digraphs with given girth, Fund. Math., 69 (1970) 227–231.

[3] L. Caccetta and R. Häggkvist, On minimal digraphs with given girth, Congressus Numerantium, 21 (1978) 181–187.

[4] Ja. Grinberg, Examples of non-Adám multigraphs, Latvian Math. Yearbook, 31 (1987) 128–138 (in Russian).

[5] Y. O. Hamidoune, A note on minimal directed graphs with given girth, J. Combin. Theory Ser. B., 43 (1987) 343–34.

[6] C. T. Hoàng and B. Reed, A note on short cycles in digraphs, Discrete Math., 66 (1987) 103–107.

[7] C. Thomassen, Counterexamples to Adam’s conjecture on arc reversals in directed graphs, J. Combin. Theory Ser. B., 42 (1987) 128–130.

[8] N. Dean and B. J. Latka, Squaring the tournament — an open problem, Congressus Numerantium, 109 (1995) 73–80.

[9] D. C. Fisher, Squaring a tournament: a proof of Dean’s conjecture, J. Graph Theory, 23 (1996) 43–48.

[10] F. Havet and S. Thomassé, Median orders of tournaments: a tool for the second neighborhood problem and Sumner’s con-jecture, J. Graph Theory, 35 (2000) 244–256.

[11] J. Shen, On the Caccetta–Häggkvist Conjecture, Graphs Combin., 18 (2002) 645–654.

[12] G. Chen, J. Shen and R. Yuster, Second neighborhood vs. first neighborhood in digraphs, Annals of Combinatorics, 7 (2003) 15–20.

[13] B. D. Sullivan, A summary of results and problems related to the Caccetta–Häggkvist conjecture, preprint, Princeton Univer-sity, 2006.

[1] B. Roy, Nombre chromatique et plus longs chemins d’un graphe, Rev. Française Automat. Informat. Rech. Opér., 1 (1967) 127–132.

[2] T. Gallai, On directed paths and circuits, in Theory of Graphs (P. Erdős and G. Katona, eds.), Academic Press, New York, 1968 115–118.

[3] T. Gallai and A. N. Milgram, Verallgemeinerung eines graphentheoretischen Satzes von Rédei, Acta Sci. Math. Szeged, 21 (1960) 181–186.

[4] G. Hahn and B. Jackson, A note concerning paths and independence number in digraphs, Discrete Math., 82 (1990) 327–329.

[5] F. Havet, Stable set meeting every longest path, Discrete Math., 289 (2004) 169–173.

[6] J. M. Laborde, C. Payan and N. H. Xuong, Independent sets and longest directed paths in digraphs, in Graphs and Other Combinatorial Topics (M. Fiedler and ed.), Teubner Verlagsgesellschaft, Leipzig, 1983 173–177.

[1] L. Lovász, On graphs not containing independent circuits (Hungarian), Mat. Lapok, 16 (1965) 289–299.

[2] L. Babai, Long cycles in vertex transitive graphs, J. Graph Theory, 3 (1979) 301–304.

[3] M. Grِtschel, On intersections of longest cycles, in Graph Theory and Combinatorics (B. Bollobas and ed.), Academic Press, London, 1984 171–189.

[4] M. Matthews and D. Sumner, Hamiltonian results in K1; 3 -free graphs, J. Graph Theory, 8 (1984) 139–146.

[5] C. Thomassen, Reflections on graph theory, J. Graph Theory, 10 (1986) 309–324.

[6] S. M. Zhan, On hamiltonian line graphs and connectivity, Discrete Math., 89 (1991) 89–95.

[7] Z. Ryjaček, On a closure concept in claw-free graphs, J. Combin. Theory Ser. B., 70 (1997) 217–224.

[8] C. Thomassen, Chords of longest cycles in cubic graphs, J. Combin. Theory Ser. B., 71 (1997) 211–214.

[9] E. Birmelé, Thèse de doctorat, Université Lyon 1, 2003.

[10] E. Birmelé, J. A. Bondy and B. A. Reed, The Erdős–Pَsa property for long circuits, Combinatorica, to appear.

[1] W. T. Tutte, On hamiltonian circuits, J. London Math. Soc., 21 (1946) 98–101.

[2] W. T. Tutte, A theorem on planar graphs, Trans. Amer. Math. Soc., 82 (1956) 99–116.

[3] J. Sheehan, The multiplicity of Hamiltonian circuits in a graph, in Recent Advances in Graph Theory (M. Fiedler and ed.), Academia, Prague, 1975 447–480.

[4] A. G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs, Ann. Discrete Math., 3 (1978) 259–268.

[5] M. Chrobak and S. Poljak, On common edges in optimal solutions to traveling salesman and other optimization problems, Discrete Appl. Math., 20 (1988) 101–111.

[6] N. Alon, Non-constructive proofs in combinatorics, in Proc. Internat. Congr. Math., Kyoto, 1990, Springer-Verlag, Tokyo, 1991 1421–1429.

[7] H. Fleischner, Uniqueness of maximal dominating cycles in 3 -regular and of Hamiltonian cycles in 4 -regular graphs, J. Graph Theory, 18 (1994) 449–459.

[8] C. Thomassen, On the number of hamiltonian cycles in bipartite graphs, Combin. Probab. Comput., 5 (1996) 437–442.

[9] C. Thomassen, Chords of longest cycles in cubic graphs, J. Combin. Theory Ser. B., 71 (1997) 211–214.

[10] C. Thomassen, Independent dominating sets and a second Hamiltonian cycle in regular graphs, J. Combin. Theory Ser. B., 72 (1998) 104–109.

[11] H. Fleischner, Uniquely Hamiltonian graphs of minimum degree four, preprint, 2004.

[12] P. Haxell, B. Seamone and J. Verstraëte, Independent dominating sets and hamiltonian cycles, preprint, 2005.