Topics in Graph Theory Math 958 Fall 2008 Class Log

1. Aug 25, Mon. course overview and logistics; Sec 3.4: list coloring definitions; example of bipartite graphs with high choice number; lemmas towards Brooks thm extension
2. Aug 27, Wed. degree-choosability; forcing even cycles with at most one chord
3. Aug 29, Fri. Brooks thm extension for list coloring; k-degeneracy
Sept 1, Mon. Labor Day, no class.
4. Sept 3, Wed. bound on choice number for bipartite graphs in terms of number of vertices; lower bound in terms of average degree; basic probabilistic method
5. Sept 5, Fri. continued lower bound in terms of average degree
6. Sept 8, Mon. finished the probabilistic proof
7. Sept 10, Wed. edge list coloring; line graphs; hereditary families; List Coloring Conjecture; kernels of digraphs; relation to list coloring
8. Sept 12, Fri. Galvin's proof of the List Coloring Conjecture for bipartite multigraphs
9. Sept 15, Mon. Shannon-type theorem for edge list coloring
10. Sept 17, Wed. Tyler Seacrest: combinatorial nullstellensatz
11. Sept 19, Fri. Tyler Seacrest: 2 applications of the combinatorial nullstellensatz
12. Sept 22, Mon. graph polynomial for coloring; calculating coefficients of given monomials; statement of Alon-Tarsi thm
13. Sept 24, Wed. calculating coefficients using circulations; proof of Alon-Tarsi theorem; statement of list coloring theorem for squares of cycles
15. Sept 26, Fri. proof of list coloring theorem for squares of cycles; Derrick Stolee: algebraic Nullstellensatz for proving infeasibility
16. Sept 29, Mon. Derrick Stolee: using Nullstellensatz to prove non-3-colorability; techniques to improve
17. Oct 1, Wed. Derrick Stolee: 3-coloring is NP-complete; planar graphs are 5-choosable
18. Oct 3, Fri. finished Thomassen proof; Mike Ferrara: potentially and forcibly H-graphic sequences
19. Oct 6, Mon. application of coloring to scheduling; Sec 3.5: circular chromatic number; application to traffic light scheduling; lower bound; cycles; relation to chromatic number
20. Oct 8, Wed. inf is a min and circular chromatic number is rational; form of the rational number
21. Oct 10, Fri. (k,d)-colorings; star chromatic number; equivalence with circular chromatic number; circular chromatic number of the Petersen graph
22. Oct 13, Mon. Katie Field: fractional hypergraph packing and covering; LP definition and t-fold definition
23. Oct 15, Wed. Katie Field: fractional chromatic number; fractional clique number; duality gap and integrality gap; fractional list chromatic number
24. Oct 17, Fri.
Oct 20, Mon. Fall break, no class.
25. Oct 22, Wed. independence ratio; Petersen graph has no (5,2)-coloring; cores; k-critical graphs are cores
26. Oct 24, Fri. cores; all cores are isomorphic; retracts; when a graph has a complete core; cores of maximal triangle-free graphs; twins
26. Oct 27, Mon. Debbie Berg: fractional matchings and fractional edge colorings
27. Oct 29, Wed. No class.
28. Oct 31, Fri. finished fractional edge colorings; basic probabilistic method; application to 2-coloring k-uniform hypergraphs
29. Nov 3, Mon. Raghunath Tewari: coloring planar graphs; discharging
30. Nov 5, Wed. Raghunath Tewari: discharging; Four Color Thm
31. Nov 7, Fri. connection between 2-coloring k-uniform hypergraphs and list coloring planar graphs; probabilistic lower bound on Ramsey numbers
32. Nov 10, Mon. introducing extra randomness: sum-free subsets and Katona's proof of the Erdos-Ko-Rado thm
33. Nov 12, Wed. linearity of expectation; random graphs; G_{n,p} model; for fixed p, G_{n,p} is almost always connected
34. Nov 14, Fri. Katie Morrison: Lovasz Local Lemma; application to list coloring
35. Nov 17, Mon. Use of Markov's Inequality for showing almost every graph is connected and has diameter 2, for fixed p; graphs exist of arbitrarily high chromatic number and girth
36. Nov 19, Wed. finished Erdos proof; Chernoff bounds
37. Nov 21, Fri. Derek Boeckner: variance, joint distributions, covariance; Chebyshev's Inequality
38. Nov 24, Mon. second moment method
Nov 26-28, Wed-Fri. Thanksgiving break, no class.
39. Dec 1, Mon. second moment method; concentration of clique number of random graph; Chantelle Bicket: Grotzsch's thm
40. Dec 3, Wed. Grotzsch's thm
41. Dec 5, Fri. Grotzsch's thm; Andrew Ray: online chromatic number
42. Dec 8, Mon. online chromatic number of trees and interval graphs
43. Dec 10, Wed. Brian Kell: chromatic polynomial
44. Dec 12, Fri. Brian Kell, continued.

    Back This page last modified .