Topics in Graph Theory

• Review of basic terms and notations in graph theory. Network flows. Ford-Fulkerson theorem. Corollary on existence of integer maximum flow in network with integer weights. [Diestel, theorem 6.2.2 and corollary 6.2.3]
• Graph factorization. Hall’s theorem (derived from integer flow theorem). König’s criterion for 1-factorization of bipartite graphs. [Diestel, Corollary 2.1.3] Petersen’s criterion for 2-factorization of arbitrary graphs. [Diestel, Corollary 2.1.5] Tutte’s criterion for 1-factorization of arbitrary graphs. [Diestel, theorem 2.2.1] Ancel’s theorem on covering complete graph with bipartite graphs. [Radhakrishnan] Graham-Pollak theorem on decomposition of complete graph into complete bipartite graphs. [Aigner]
• Concepts of edge and vertex k-connectivity. [Emelichev, §33] Menger’s theorem (derived from integer flow theorem). [Swamy, section 15.7.4] Mader’s theorem. [Diestel, theorem 1.4.3]
• Theorem on six properties of 2-connected graphs. [Emelichev, theorem 34.1] Fan lemma. Theorem on cycles in k-connected graphs. [Bondy, section 9.2] Theorems on recursive construction of 2-connected and 3-connected graphs. [Diestel, proposition 3.1.1, theorem 3.2.3] Minimal connected graphs: trees. Theorem on six equivalent definitions of trees. Block and cut-vertex trees: BC-trees. [Emelichev, propositions 34.2-34.6] Metrics on trees. [Zaretskiy][Zykov, §21]
• Graph embeddings. Planar graphs. [Emelichev, §36-37] Minors and topological minors. [Diestel, section 1.7] Maximum number of edges in planar graphs. [Emelichev, §36-37] Wagner and Kuratowski criteria. [Skopenkov]
• Planar triangulations. 3-connectivity of triangulations. [Emelichev, §38, corollary 39.2] Tutte’s theorem on face boundaries in 3-connected planar graphs. Whitney’s theorem. [Bondy, theorems 10.27, 10.28]
• Wagner-Fáry theorem on straight-line embeddings of planar graphs. Several theorems without proof on properties of planar graphs. Minor-hereditary graph classes, Seymour-Robertson theorem (without proof). [Diestel, corollary 12.5.2]
• Menger’s theorem analogues for quasi-triangulations. Separators in planar graphs. [AlonSeymourThomas]
• Definitions of chromatic number, chromatic index and list chromatic number. Relationship between list and regular chromatic numbers. Simple bounds on chromatic number: bounds via clique number, independence number, number of edges. [Diestel, proposition 5.2.1; Emelichev, corollary 54.2 etc.] Relationship between list chromatic number and vertex degrees. [Alon] Brooks’ theorem on chromatic number. [Emelichev, p. 239] Vizing’s and König’s theorems on chromatic index. [Diestel, proposition 5.3.1, theorem 5.3.2]
• List chromatic number of planar graphs: Voigt and Thomassen theorems [Aigner, chapter 34].
• Non-locality of chromatic number. Zykov-Mycielski construction: sequence of triangle-free graphs with large chromatic number. [Emelichev, theorem 54.5] Erdős’ theorem on graphs with arbitrarily large girth and chromatic number. [Diestel, theorem 11.2.2] Corollary on existence of graphs with arbitrarily large girth and connectivity. [Diestel, corollary 11.2.3]
• Perfect graphs. Examples. Lovász theorem (weak Berge perfect graph conjecture). [Diestel, theorem 5.5.6]
• Extremal problems in graph theory. Turán’s theorem. Erdős-Stone-Simonovits theorem. [Conlon]
• Hamiltonian cycles. Chvátal-Erdős conditions. [Diestel, proposition 10.1.2] Asratian-Khachatrian conditions. [Diestel, theorem 10.1.3] Hamiltonian sequences, Chvátal’s conditions. [Diestel, theorem 10.2.1] Hamiltonian cycles in planar graphs. Grinberg’s theorem. [Emelichev, theorem 44.7]

Materials

• Lecture Slides
• Interactive Course Map

Bibliography

• V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, R. I. Tyshkevich. Lectures on Graph Theory. Moscow: Librokom, 2009.
• K. A. Zaretskiy. Construction of a Tree from Distances Between Pendant Vertices // Russian Mathematical Surveys, 1965, volume 20, issue 6(126), pp. 90-92
• A. A. Zykov. Theory of Finite Graphs. Novosibirsk: Nauka, 1969.
• M. Swamy, K. Thulasiraman. Graphs, Networks and Algorithms. Moscow: Mir, 1984.
• A. B. Skopenkov. Around Kuratowski’s Planarity Criterion // Mathematical Education, 2005, issue 9, pp. 116-128
• M. Aigner, G. M. Ziegler. Proofs From THE BOOK. Fourth Edition. Springer, 2009.
• N. Alon. Degrees and choice numbers // Random Structures and Algorithms, 16(2000), 364-368.
• N. Alon, P. D. Seymour and R. Thomas. Planar separators, SIAM J. Discrete Math. 7 (1994), 184-193.
• B. Bollobás. Modern Graph Theory. Springer, 1998.
• J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, 2008.
• D. Conlon. Extremal Graph Theory Course. Lecture notes.
• R. Diestel. Graph Theory. Fourth Edition. Springer-Verlag, 2010.
• J. Radhakrishnan. Entropy and Counting // IIT Kharagpur, Golden Jubilee Volume on Computational Mathematics, Modelling and Algorithms. New Delhi, 2001.