Math 4995 Graph Theory II
Syllabus–Semester I 1999-2000
- Rapid Review of Graph Theory I.
- Matchings and coverings in bipartite graphs.
- Systems of distinct representatives.
- An existance criterion — Hall’s theorem.
- Minimum vertex covering of edges and maximum matching — König’s theorem.
- Ear assemblies for 3-connected graphs
- 3-connected graphs.
- Topological equivalence of graphs.
- Topologically 3-connected graphs.
- Essential vertices in a topologically 3-connected graph.
- Threads. Deletion of threads.
- Topologically induced subgraphs.
- Every top 3-connected graph contains Top K_4.
- Every top 3-connected graph is the union of the subgraph induced by the essential vertices together with nontrivial threads.
- G-admissible paths where G is a topologically 3-connected graph.
- Ear assembly of a 3-connected graph.
- Ear assemblies which preserve a given vertex set.
- Graph planarity
- Various embeddings of a graph into a plane.
- Geometrical duality of graphs.
- Euler’s formula.
- Minimal non-planar graphs.
- Kuratowski’s planarity criterion.
- Eulerian Graphs
- Walks, trails and paths and cycles.
- Euler trails and Euler circuits.
- Characterizations of Eulerian graphs and digraphs.
- Fleury’s algorithm.
- Minimum coverings of a graph by Euler trails.
- Labyrinth problems.
- The arborescence generated by an Euler cycle and the mumber of Euler circuits of an Eulerian digraph.
- Chinese postman problems.
- Hamiltonian Graphs
- Hamiltonian paths and cycles.
- Graph closure.
- Sufficient conditions for a hamiltonian cycle.
- Maximal non hamiltonian graphs.
- Dirac’s [1952] theorem on longest cycles.
- Claw free graphs
- Chvátal conjecture: Every 2-tough graph is hamiltonian.
- A closure operation on claw free graphs
- Equivalence of the following conjectures in a 4-connected graph.
- If $G$ is claw free then $G$ is hamiltoniam.
- If $G$ is a line graph then $G$ is hamiltomian.
- If $G$ is the line graph of a triangle free graph, then $G$ is hamiltonian.
- A 7-connected claw free graph is hamiltonian.
Text
- J.A. Bondy and U.S.R. Murty, Graph Theory With Applications, North Holland, Amsterdam, 1976.
Bibliography
- D.B. West, Introduction to Graph Theory, Prentice Hall, 1996.
- B. Bollobás, Extremal Graph Theory, Academic Press, 1978.
- M. Behzad, G. Chartrand, and Linda Lesniak–Forest, Graphs and Digraphs, Wadsworth International Group, 1981.