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

[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.