CSE 421N: Basic Graph Theory

Contact:

Dr. Masud Hasan

Room: CSE 657, Phone: x7738

Email: masudhasan AT cse DOT buet DOT ac DOT bd

Announcements:

• Class Test 1: 19/08/2008 (Tuesday, in class). Syllabus: [West] 1.1.1 to 2.1.15, see detail below.

• Class Test 2: 07/09/2008 (Sunday, in class). Syllabus: [West] Chapter 4, see detail below.

• Class Test 3: 14/10/2008 (Tuesday, in class). Syllabus: Graph Coloring: [West] Chapter 5, Chapter 7.1 (Edge coloring); see detail below.

• Class Test 4 (and may be 5 too): 02/11/2008 (Sunday, in class). Syllabus: [West] Chapter 6: Planar Graphs; see detail below

Class Test marks:

• Class Test Marks

• Class Test 1 Answer sheet

• Class Test 2 Answer sheet

• Class Test 3 Answer sheet

Text reading:

• [West] Introduction to Graph Theory, by Douglas B. West, 3^rd edition

• [Diestel] Graph Theory, by Reinhard Diestel, Electronic Edition 2005

• [Corman] Introduction to Algorithms, by Coreman, Leiserson, Rivest, and Stein, 2nd Edition

• ClassNote

Syllabus:

• Related pre and post ambles of sections/bullets are by default included

• Class notes are by default included

• [West] Chapter 1: Fundamental Concepts

  1.1.1-1.1.21, 1.1.27-1.1.28, 1.1.30-1.1.40

  1.2.2-1.2.19, 1.2.24-1.2.31

  1.3.1-1.3.6, 1.3.10, 1.3.13, 1.3.15-1.3.16

  All related (-) marked exercise

• [West] Chapter 2: Trees and Distances

  2.1.1-2.1.5, 2.1.8-2.1.13, 2.1.15

  All related (-) marked exercise

• [West] Chapter 4: Connectivity and Paths

  4.1.1-4.1.2, 4.1.7-4.1.8, 4.1.9 (proof from Harary: page 43-44), 4.1.10, 4.1.11, 4.1.16-4.1.20

  4.2.1-4.2.8

  All related (-) marked exercise

• [West] Chapter 5: Coloring of Graphs

  5.1.1-5.1.8, 5.1.12-5.1.17

  All related (-) marked exercise

• [West] Chapter 7: Edges and Cycles

  Edge Coloring: 7.1.2-7.1.3, 7.1.6, 7.1.7 (for proof also see Diestel, page 119 and class note), 7.1.10 (without proof)

  Hamiltonian Cycle: 7.2.1-7.2.5, 7.2.7, 7.2.8 (for proof also see Diestel, page 276 and class note)

  All related (-) marked exercise

• [West] Chapter 6: Planar Graphs

  6.1.1-6.1.2, 6.1.4, 6.1.7-6.1.13, 6.1.16-6.1.27 (get the proof of 6.1.20 here)

  6.2.1-6.2.2

  6.3.1

  All related (-) marked exercise

• Chinese Postman Problem

  Class Note

• Chromatic Polynomial

  [West] 5.3.1-5.3.7, 5.3.11

• Perfect Graphs

  Class Note

  [Diestel] From page 116 (2nd last para) to page 117 (Theorem 5.2.5 (without proof)), 5.5 (up to Proposition 5.5.1 (exclusive))

  [West] 5.3.18-5.3.21 (only bi-partite graphs), 8.1.1