Difference between revisions of "Math 355: Graph Theory"
(→Prerequisites) |
(→Prerequisites) |
||
| (24 intermediate revisions by 2 users not shown) | |||
| Line 11: | Line 11: | ||
=== Prerequisite === | === Prerequisite === | ||
| − | [[Math | + | [[Math 213]]. |
=== Description === | === Description === | ||
| − | + | Graphs and subgraphs, coloring problems, applications. | |
== Desired Learning Outcomes == | == Desired Learning Outcomes == | ||
| Line 20: | Line 20: | ||
=== Prerequisites === | === Prerequisites === | ||
| − | Math | + | [[Math 213]]. |
=== Minimal learning outcomes === | === Minimal learning outcomes === | ||
| − | + | Definition of a graph, examples (trees, paths, cycles, Petersen graph, etc.), First Theorem of Graph Theory, isomorphisms of graphs and graph invariants, chromatic number, connectivity, planar graphs and conditions for planarity, statements of Four Color Theorem and Kuratowski's theorem, Hamiltonian cycles. | |
| + | |||
| + | Additional topics from 1) proof of Kuratowski's theorem, 2) definition of the Euler characteristic and proof of Euler's formula for the genus, 3) proof of the Chvatal-Erdos theorem on the existence of Hamiltonian cycles. | ||
<div style="-moz-column-count:2; column-count:2;"> | <div style="-moz-column-count:2; column-count:2;"> | ||
| Line 31: | Line 33: | ||
Possible textbooks for this course include (but are not limited to): | Possible textbooks for this course include (but are not limited to): | ||
| − | * ''Graph Theory'' by Rusell Merris | + | * ''Graph Theory'' by Rusell Merris (Chap. 1-5). |
| − | + | ||
| − | + | ||
A good additional resource is An Introduction to Graph Theory by Douglas B. West, but the book is probably too encyclopedic to use as a main text. | A good additional resource is An Introduction to Graph Theory by Douglas B. West, but the book is probably too encyclopedic to use as a main text. | ||
=== Additional topics === | === Additional topics === | ||
| − | Possible other topics include spectral theory of graphs. | + | |
| + | |||
| + | Possible other topics include spectral graph theory (networkings, expanders, Ramanujan graphs), characterization of Ramanujan graphs by the Riemann hypothesis for its zeta function. A good source for this topic is the paper by M. Ram Murty, Ramanujan Graphs, J. Ramanujan Math. Soc. 18(2003) 1-20. | ||
=== Courses for which this course is prerequisite === | === Courses for which this course is prerequisite === | ||
[[Category:Courses|355]] | [[Category:Courses|355]] | ||
Latest revision as of 14:24, 22 August 2019
Contents
Catalog Information
Title
Graph Theory.
(Credit Hours:Lecture Hours:Lab Hours)
(3:3:0)
Offered
W
Prerequisite
Description
Graphs and subgraphs, coloring problems, applications.
Desired Learning Outcomes
Prerequisites
Minimal learning outcomes
Definition of a graph, examples (trees, paths, cycles, Petersen graph, etc.), First Theorem of Graph Theory, isomorphisms of graphs and graph invariants, chromatic number, connectivity, planar graphs and conditions for planarity, statements of Four Color Theorem and Kuratowski's theorem, Hamiltonian cycles.
Additional topics from 1) proof of Kuratowski's theorem, 2) definition of the Euler characteristic and proof of Euler's formula for the genus, 3) proof of the Chvatal-Erdos theorem on the existence of Hamiltonian cycles.
Textbooks
Possible textbooks for this course include (but are not limited to):
- Graph Theory by Rusell Merris (Chap. 1-5).
A good additional resource is An Introduction to Graph Theory by Douglas B. West, but the book is probably too encyclopedic to use as a main text.
Additional topics
Possible other topics include spectral graph theory (networkings, expanders, Ramanujan graphs), characterization of Ramanujan graphs by the Riemann hypothesis for its zeta function. A good source for this topic is the paper by M. Ram Murty, Ramanujan Graphs, J. Ramanujan Math. Soc. 18(2003) 1-20.
