Friday 9:00 - K10C
Recitations Friday 10:40 - K10C
Literature:
R. Diestel: Graph Thoery, available on-line on flooved.
T. Valla: Skripticka z kombinatoriky
M. Hall: Combinatorial Theory, Wiley 1986
My handouts from previous years might be useful, they can be found in SIS.
OCT 4, 2024 recitations
OCT 11, 2024
Hall Theorem on Systems of Distinct Representatives
Set systems, systems of distinct representatives, Hall's theorem.
Applications - matchings in bipartite graphs, extending Latin rectangles to Latin squares.
Maximum matching and minimum vertex cover in bipartite graphs.
Independent sets and covering lines in matrices (on the way to Birkhoff Theorem on bistochastic matrices, to be done during the recitations).
OCT 11, 2024 recitations
OCT 18, 2024
Matchings in general graphs
Maximal, maximum and perfect matchings in a graph. Maximum matchings and augmenting paths. Tutte's theorem on the existence of a perfect matching in a graph.
Petersen's theorem on perfect matchings in cubic edge-2-connected graphs.
OCT 18, 2024 recitations
OCT 25, 2024
Edmonds's algorithm for maximum matching in a general graph
OCT 25, 2024 recitations
NOV 1, 2024
Chooseability of graphs
List colorings and chooseability. Chooseability of subclasses of planar graphs.
Bounds on chooseability via orientations with kernels.
NOV 1, 2024 recitations
NOV 8, 2024
Graph Coloring and Chooseability II
Coloring graphs on surfaces of higher (orientable) genus - Heawood Theorem. Edge coloring - Vizing Theorem. Chooseability of line graphs of bipartite graphs
(i.e., edge-chooseability of bipartite graphs).
NOV 8, 2024 recitations
NOV 15, 2024
Planar graphs
Some lemmas on drawings of planar graphs. Lemma about edge-contraction in 3-connected graphs. Proof of Kuratowski theorem.
NOV 15, 2024 recitations
Home assignment scores
| Nick | 1.1 | 1.2 | 1.3 | 2.1 | 2.2 | 2.3 | 3.1 | 3.2 | 3.3 | 4.1 | 4.2 | 4.3 | Total |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Zaba | 1 | 1 | 1 | 1 | 1 | 1 | 6 | ||||||
| kokostra grafu | 1 | 1 | 1 | 3 | |||||||||
| Rikam_chtel-by | 1 | 1 | 1 | 3 | |||||||||
| {0,{0}} +2 | 1 | 1 | 1 | 3 | |||||||||
| 11010 | 1 | 1 | 1 | 3 | |||||||||
| Ctyrlistek | 1 | 1 | 1 | 3 | |||||||||
| kopretina | 1 | 1 | 1 | 3 | |||||||||
| Banas | 1 | 1 | 1 | 3 | |||||||||
| Zulu | 1 | 1 | 1 | 3 | |||||||||
| ancapatoru | 1 | 0 | 1 | 2 |