Graph theory

Description
Class meetings: Lecture Mon 12:00-13:30 (Room 3.517). If you have any questions, you can email me to set up an appointment.

Grading: The final grade consists of two components. First, at the end of the semester there will be an oral exam covering the lecture material. In addition, each student will be required to give a 30-minute presentation on a preassigned topic and to prepare a 1-2 page written summary of it.

Lecture notes
A. Frank. Connections in Combinatorial Optimization.
A. Frank. Gráfelmélet (in Hungarian).

Presentations
Please use the template available here.

Week 1
We proved Lovász’s undirected splitting-off theorem. As a corollary, we obtained a constructive characterization of $2k$-edge-connected graphs and proved Nash-Williams’ orientation theorem. Given a graph $G$G, we gave a necessary and sufficient condition for the existence of a degree-prescribed graph $H$ such that $G+H$ is $2k$-edge-connected. Building on this result, we characterized the minimum number of edges required to augment the edge-connectivity to $2k$ (Section 4 of the lecture notes and Sections 8.1, 8.2, 9.2.1, 11.1.1, and 11.1.2 of Frank’s book).

Week 2
We proved Galvin’s theorem on the list-coloring of bipartite graphs. We then introduced the notion of kernels in digraphs and proved the theorem of Sands, Sauer, and Woodrow on kernels in the union of two transitive acyclic digraphs. Based on this result, we showed that any digraph not containing a directed cycle of odd length has a kernel. Finally, we proved that if a graph admits a kernel-perfect orientation in which the outdegree of each vertex is at most the size of its color list minus one, then the graph has a proper list coloring (Section 6.2 of the lecture notes).

Week 3
The lecture was cancelled.

Week 4
We proved the Lucchesi-Younger theorem on the minimum size of a dijoin using the uncrossing technique. We then discussed applications, including the disjoint directed paths problem in planar acyclic digraphs. We closed the lecture by mentioning Woodall’s conjecture, together with some partial results (Section 7.1 of the lecture notes and Section 9.7.1 of Frank’s book).

Week 5
We considered the disjoint paths problem in undirected and directed graphs. We briefly summarized the hardness results and then, as an application, showed that if $D=(V, A)$ is a digraph with root $r$ and $u\in V$, the problem of finding two edge-disjoint arborescences rooted at $r$ and spanning $V$ and $V-u$, respectively, is NP-complete. As positive results, we showed that the natural cut conditions are sufficient when there are two terminal pairs, and when the supply graph is planar, the union of the supply and demand graphs is Eulerian, and all terminals lie on one face of the supply graph (Remark 3.9 in this paper, Sections 8.1 and 8.2 of the lecture notes and Sections 2.5.5 and 8.4.1 of Frank’s book).