This module introduces network flows, focusing on the max flow mincut theorem, a fundamental concept in network flow theory.
This module introduces the essential concepts of vertex cover and independent sets, foundational elements in graph theory. Understanding these concepts is crucial for solving various graph-related problems.
Students will explore:
In this module, students will delve into matchings, focusing on König's theorem and Hall's theorem. These theorems provide critical insights into the nature of matchings in bipartite graphs.
This module continues the discussion on matchings, expanding on Hall's theorem and its various applications. Students will learn how to apply these concepts in real-world situations.
This module introduces Tutte's theorem, which provides criteria for the existence of a perfect matching in graphs. Understanding this theorem is essential for advanced topics in graph theory.
Continuing with Tutte's theorem, this module discusses further implications and applications, reinforcing the understanding of perfect matchings in various types of graphs.
This module elaborates on matchings, discussing various techniques and approaches for finding matchings in different types of graphs. Students will gain practical skills in applying these concepts.
This module covers the concepts of dominating sets and path covers, essential tools in graph theory that have numerous applications in network analysis and optimization.
This module introduces the Gallai-Milgram theorem and Dilworth's theorem, two fundamental results in combinatorial optimization and graph theory that have powerful implications.
This module discusses connectivity in graphs, focusing on 2-connected and 3-connected graphs. Students will learn the importance of connectivity in graph theory and its implications.
This module explores Menger's theorem, a fundamental result in connectivity theory that provides conditions for the existence of independent paths between vertex pairs.
This module provides additional insights into connectivity, specifically focusing on k-linkedness. Students will learn about the significance of k-linkedness in graph theory.
This module discusses minors and topological minors in graphs, exploring their properties and implications in graph theory, including their relevance to connectivity.
This module introduces vertex coloring, specifically focusing on Brooks' theorem, which provides insights into the chromatic number of certain graphs.
This module continues the exploration of vertex coloring, discussing more complex aspects and applications of vertex coloring in various types of graphs.
This module introduces edge coloring and Vizing's theorem, which provides a crucial upper bound on the chromatic index of a graph.
This module dives deeper into Vizing's theorem, including its proof and an introduction to planarity, a key concept in graph theory.
This module covers the concept of coloring planar graphs, focusing on the 5-coloring theorem and Kuratowski's theorem, which are fundamental results in graph theory.
This module focuses on the proof of Kuratowski's theorem and the concept of list coloring, providing insights into its applications in graph theory.
This module discusses the list chromatic index, a crucial concept in edge coloring and its implications for various applications in graph theory.
This module introduces the adjacency polynomial of a graph and its relationship to combinatorial Nullstellensatz, providing insights into polynomial methods in graph theory.
In this module, students will learn about the chromatic polynomial and k-critical graphs, diving deeper into graph coloring concepts and their implications.
This module introduces the Gallai-Roy theorem, acyclic coloring, and Hadwiger's conjecture, providing essential insights into advanced graph coloring concepts.
This module focuses on examples of perfect graphs, exploring their properties and applications in various fields, reinforcing the concepts learned in previous modules.
This module discusses interval graphs and chordal graphs, highlighting their properties and significance in graph theory, along with real-world applications.
This module provides a proof of the weak perfect graph theorem (WPGT), exploring its implications and significance in graph theory.
This module presents a second proof of the weak perfect graph theorem and discusses some non-perfect graph classes, broadening the understanding of graph theory.
This module explores additional special classes of graphs, discussing their properties and applications in various fields, and reinforcing the concepts learned throughout the course.
This module discusses concepts of boxicity, sphericity, and Hamiltonian circuits, exploring their significance and applications in graph theory.
This module continues the discussion on Hamiltonicity, focusing on Chvátal's theorem and its implications for Hamiltonian graphs.
This module provides a comprehensive review of Chvátal's theorem, toughness, Hamiltonicity, and the 4-color conjecture, tying together essential concepts in graph theory.
This module introduces network flows, focusing on the max flow mincut theorem, a fundamental concept in network flow theory.
This module continues the exploration of network flows, discussing circulations, their properties, and applications in network theory.
This module discusses circulations and tensions in graphs, exploring their properties and implications in network flow theory.
This module delves deeper into circulations and tensions, discussing flow numbers and Tutte's flow conjectures, enhancing the understanding of network flows.
This module introduces random graphs and probabilistic methods, providing a foundation for understanding random structures in graph theory.
This module delves into the probabilistic method, discussing Markov's inequality and Ramsey numbers, crucial concepts in combinatorial theory.
This module focuses on the probabilistic method, discussing graphs of high girth and high chromatic number, important topics in random graph theory.
This module discusses the second moment method and Lovasz local lemma, providing techniques for analyzing random structures in graphs.
This module introduces graph minors and Hadwiger's conjecture, exploring their implications for graph structure and connectivity.
This module provides further insights into graph minors, discussing tree decompositions and their applications in understanding graph structure.