|
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 Tue, December 16, 2008 at 11:41am. |