#### Math 7405 Advanced Graph Theory Spring 2016 Class Log

 1. Jan 20, Wed. course overview and logistics; initial student survey; Sec 3.4: list coloring, basic definitions, simple bounds; separation of chromatic and list chromatic numbers; greedy coloring 2. Jan 25, Mon. degree choosability; conditions that imply degree choosability 3. Jan 27, Wed. characterization of degree choosable graphs, Gallai trees; Brooks-type theorem for list chromatic number; connection between non-k-choosable bipartite graphs and non-2-colorable k-uniform hypergraphs 4. Feb 1, Mon. finished connection between non-k-choosable bipartite graphs and non-2-colorable k-uniform hypergraphs; upper bound on list chromatic number of balanced complete bipartite graphs; started lower bound on list chromatic number of graphs in terms of average degree, reduced to bipartite graphs with specified min degree 5. Feb 3, Wed. finished lower bound on list chromatic number of graphs in terms of average degree for bipartite graphs 6. Feb 8, Mon. planar graphs are 5-choosable; kernels and kernel-perfect digraphs; implication for choosability 7. Feb 10, Wed. Thm 2.4.39 every digraph with no odd cycle has a kernel; bipartite planar graphs are 3-choosable 8. Feb 15, Mon. edge list coloring; List Coloring Conj; Galvin proof of Dinitz conjecture 9. Feb 17, Wed. Combinatorial Nullstellensatz; statement and proof 10. Feb 22, Mon. graph polynomial; interpretation of coefficients in terms of orientations 11. Feb 24, Wed. circulations; Alon-Tarsi theorem; list-3-coloring the squares of cycles 12. Feb 29, Mon. Sec 3.1: color critical graphs; basic properties: min degree, edge-connectivity, every vertex cut is a clique; generalized Hajos construction; conjectured edge-bound 13. Mar 2, Wed. Nathan presented on applications of the Combinatorial Nullstellensatz 14. Mar 7, Mon. potential method for proving edge-bound of 4-critical graphs 15. Mar 9, Wed. continued proof; application to Grotzsch thm 16. Mar 14, Mon. class cancelled 17. Mar 16, Wed. Jason presented on expected run time of backtracking for coloring; column generation algorithm for coloring 18. Mar 28, Mon. guest Peter Erdos; lecture on sampling degree sequences via Markov Chain Monte Carlo 19. Mar 30, Wed. Sec 3.6: discharging; 6-color thm and 5-color thm viewed as discharging proofs; typical charges on planar graphs; planar graphs of girth at least 6 using balanced charging 20. Apr 4, Mon. discharging proof for bound on list chromatic number of the square, under max degree and Mad conditions 21. Apr 6, Wed. Duong presented two short proofs of Grotzsch's thm 22. Apr 11, Mon. Vizing's Planar Graph Conj; proof towards that 23. Apr 13, Wed. list choosability of planar graphs 24. Apr 18, Mon. Luke presented on the best-known partial result toward Steinberg's conjecture 25. Apr 20, Wed. Chase presented on Kastelyn's method for counting perfect matchings in planar graphs 26. Apr 25, Mon. Regularity Lemma; Embedding Lemma 27. Apr 27, Wed. proof of Erdos-Stone; proof sketch of the Regularity Lemma 28. May 2, Mon. Eric presented on graph Ramsey numbers using the Regularity Lemma 29. May 4, Wed. Removal Lemma; Roth's theorem on 3-term arithmetic progressions; corners in matrices