Course: MCS 423, Graph Theory

CRN: 38586 and 38587

Time: MWF 1100-1150am

Place: 2Lincoln Hall 101

Professor: Dhruv Mubayi

Office: 620 SEO

Tel: 3-8036

E-mail: mubayi@uic.edu

Course Web Page: http://www.math.uic.edu/~mubayi/423/Fall17/423Fall17info.html

Office Hours: M, F: 1:45-2:45 or by appointment

Grader: Mohsen Aliabadi; email: mohsenmath88@gmail.com

Grader Office Hours: M 8-9 and F 4-5 in MLC (SEO 430)

Grading Policies:

Attendance and class participation: 15%

Homework (Due Friday every two weeks): 20%

Two in-class midterms, 15% each: 30%

Final Exam: 35%

Be sure to staple your homework. No late homework will be accepted.

Disability Policy: Students with disabilities who require accommodations for access and participation in this course must be registered with the Office of Disability Services (ODS). Please contact ODS a 312/413/-2183 (voice) or 312/413-0123 (TTY).

Prerequisite: GRADE OF C OR BETTER IN MCS 261 OR EECS 360; AND MATH 310 OR 320 OR 330.

Description: The fundamentals of graph theory: trees, connectivity, Euler tours, Hamilton cycles, matchings, colorings and Ramsey theory. Although applications and some graph algorithms will be included, the course will focus on understanding the structure and properties of graphs as independent objects of study. We will attempt to cover most of Chapters 1--7 and Section 8.3 from the text.

Text: West, Introduction to Graph Theory, Second Edition, Prentice Hall.

Homework 1, Due Friday September 8

Section 1.1: 2--9, 18, 26, 27, 34

Homework 2, Due Friday September 22

Section 1.2: 1, 7, 8, 10, 20, 40

Section 1.3: 1, 2, 7, 8 b d, 9, 17, 31

Section 1.4: 4, 5, 7, 8, 26

Homework 3, Due Friday October 6

Section 2.1: 2, 4, 15, 18, 40

Section 2.2: 1, 2, 3

Section 2.3: 1, 2, 3, 6

Test 1 -- Friday Oct 13

Homework 4, Due Friday October 20

2.3: 10

3.1: 1, 2, 3, 5, 7, 8, 11, 19, 29

3.2: 4

Homework 5, Due Friday November 3

3.3: 1, 4, 6, 19, 22

4.1: 3, 4, 6, 8, 28

Homework 6, Due Friday November 17

4.2: 1, 2, 4, 11, 20, 23, 24

4.3: 1, 6, 7, 10, 12

5.1: 1, 2, 3, 7, 12, 39

TEST 2 -- Friday December 1

Homework 7, Due Wednesday Dec 6 (last homework)

5.2: 7, 12a

6.1: 10, 12, 26c

6.2: 4

7.1: 2, 4

7.2: 3, 7, 25