Instructor

Sudebkumar Prasant Pal (spp@cse.iitkgp.ac.in)

Teaching Assistant

Koustav De (koustavde7@kgpian.iitkgp.ac.in)

Tentative Syllabus as per course specifications

Basic Concepts: Graphs and digraphs, incidence and adjacency matrices, isomorphism, the automorphism group;

Trees: Equivalent definitions of trees and forests, Cayleys formula, the Matrix-Tree theorem, minimum spanning trees;

Connectivity: Cut vertices, cut edges, bonds, the cycle space and the bond space, blocks, Menger's theorem;

Paths and Cycles: Euler tours, Hamilton paths and cycles, theorems of Dirac, Ore, Bondy and Chvatal, girth, circumference, the Chinese Postman Problem, the Travelling Salesman problem, diameter and maximum degree, shortest paths;

Matchings: Berge's Theorem, perfect matchings, Hall's theorem, Tutte's theorem, Konig's theorem, Petersen's theorem, algorithms for matching and weighted matching (in both bipartite and general graphs), factors of graphs (decompositions of the complete graph), Tutte's f-factor theorem;

Extremal problems: Independent sets and covering numbers, Turan's theorem, Ramsey theorems;

Colorings: Brook's theorem, the greedy algorithm, the Welsh-Powell bound, critical graphs, chromatic polynomials, girth and chromatic number, Vizing's theorem;

Graphs on surfaces: Planar graphs, duality, Euler's formula, Kuratowski's theorem, toroidal graphs, 2-cell embeddings, graphs on other surfaces;

Directed graphs: Tournaments, directed paths and cycles, connectivity and strongly connected digraphs, branchings;

Networks and flows: Flow cuts, Max flow min cut theorems, perfect square;

Selected topics: Dominating sets, the reconstruction problem, intersection graphs, perfect graphs, random graphs.


Course Logistics



Coursework

Coverage

02.08.2023 Introduction to basic terminologies; Definition of Graphs, Graph representation; Graph isomorphism; Paths, Cycles; Bipartite graphs; Necessary and sufficient condition for the existence of an Eulerian Tour in a graph
03.08.2023 Introduction to (i) matchings, (ii) planar embeddings of some classes of graphs, (iii) chromatic number, (iv) Eulerian and Hamiltonian cycles
04.08.2023 Petersen Graph; Hall's condition : A bipartite graph G[X,Y] has a matching that saturates X ⇔ ∀S⊆ X : |N(S)| ⩾ |S|; Corollary : A bipartite has a perfect matching ⇔ |X| = |Y| and ∀S⊆ X : |N(S)| ⩾ |S|, Every regular non-empty bi-partite graph has a 1-factor or perfect matching(Use Hall's theorem towards a direct proof), Statement of Tutte's theorem[1947]; Examples of Interval graphs; Relationship between chromatic number and clique number for spacial classes of graphs; Problems : Count the number of 5-cycles in Petersen graph; Show that if the girth of a graph G is 5 and δ(G) = k, then show that |V(G)| ⩾ k2 + 1; Given two graphs when do we say that they are isomorphic or identical; Mantel's theorem[1907] : The max #edges in an n-vertex triangle-free simple graph is ⌊n2 / 4⌋
09.08.2023 Count the number of C4’s in K3,3; Why does the Petersen Graph have no triangle? Counting the number of 5-cycles and 6-cycles in the Petersen Graph; Definitions of Chordal graphs; Drawing all the possible induced subgraphs of the ‘Kite’; Definition of Perfect graphs; A graph with |E| edges has at least |V| - |E| connected components.
10.08.2023 Definition of a Stable set, Vertex cover; Vertex covers and stable sets are complementary; Bounding the number of edges using α(G) and β(G) for triangle-free graphs; Graphs with small sized maximum matchings; vertex covers and maximum matchings; 2-factor approximation for vertex covering;
11.08.2023 Solutions/hints for the problems given in Tutorial 1 and Homework 1;
23.08.2023 Vertex covers, edge covers; the product α(G)ω(G) for Petersen, bipartite, complements of bipartite, complete, cycle and other simple graphs, verifying that such products are at least as large as the number of vertices in perfect graph examples; Gallai's Theorem; maximal and maximum matchings; augmenting paths, alternating paths; symmetric difference of two matchings;
24.08.2023 Perfect matchings in general simple connected graphs; Petersen graph is not bipartite, It has a perfect matching and a minimum edge cover of the same size 5; Example of a connected graph with an even number 20 of vertices but a maximum matching of size only 9; Illustration of Tutte's condition for paw, claw, kite, K3,3, triangle, K5, K2.4; Dense graph that are maximal perfect matching deficient; bad sets give such dense graphs; dense graphs exist for bad sets when there are no perfect matchings.
25.08.23 Tutte's theorem; Proof of Hall's theorem; Proof of Berge's theorem; Proof of Gallai's theorem; application of Tutte's theorem
30.08.2023 Circles and pair-wise common tangents between circles, of K2,4 and no K2,5 in circle-tangent incident graphs; definition of dominating set; k-regular graphs of girth four; bounds on the chromatic number of a graph; Prove that every n-vertex graph with minimum degree k has a dominating set of size at most n((1 + ln(k+1))⁄(k+1))
06.09.2023 Large number of edges lead to subgraphs with proportionate minimum vertex degree i.e., an n vertex graph G=(V,E) with |E| ⩾ (c-1)n contains a subgraph H with δ(H) ⩾ c; Extremal results such as spanning subgraphs of high vertex degrees, every graph G has a bipartite spanning subgraph B such that ∀ v ∈ V(G), dB(v) ⩾ dG(v) / 2; perfect matching is a spanning subgraph; In BFS trees of bipartite graphs of large degree, the sets reachable grow rapidly; Extremal results: Mantel's theorem, bounding triangles in a graph, we can show that the number of triangles in any simple graph of n vertices and m edges is at least (4m / 3n)(m - n2 / 4); The maximal graph idea for proving Tutte's theorem; Properties of the universal set of vertices of a maximally saturated graph with no perfect matching.
08.09.2023 Scribe Note by Anirudh M.
14.09.2023 Scribe Note by Bhagoti
27.09.2023 Tightness of the upper bound of the chromatic number χ(G) in terms of maxGδ(G) where G is any induced subgraph of G and δ(G) is the minimum degree of a vertex in G. Enumerating vertices of a graph G like Hn-1 = G ∖ { xn }, Hn-2 = Hn-1 ∖ { xn-1 } = G ∖ { xn, xn-1 }, … where xn is a vertex with deg(xn) ≤ maxGδ(G); we can Greedily color vertices in the order of the sequence x1, x2, …, xn; This result can be exploited for non Δ-regular graphs as maxGδ(G) ≤ Δ - 1 making χ(G) ≤ Δ; Every graph G with m edges satisfy χ(G) ⩽ 1⁄2 + √(2m + 1⁄4); the least number k such that G has a vertex enumeration in which each vertex is preceded by fewer than k of its neighbours is called the coloring number col(G) of G; So, χ(G) ⩽ col(G) ⩽ maxGδ(G) + 1; [Brooks 1941] Let G be a connected graph. If G is neither complete nor an odd cycle, then χ(G) ⩽ Δ(G); A graph G is perfect if and only if |H| ⩽ α(H) · ω(H) ∀ induced subgraphs H ⊆ G. To show that chordal graphs are perfect, we shall first characterize their structure. If G is a graph with induced subgraphs G1, G2 and S, such that G = G1 ∪ G2 and S = G1 ∩ G2, we say that G arises from G1 and G2 by pasting these graphs together along S. A graph is chordal if and only if it can be constructed recursively by pasting along complete subgraphs, starting from complete graphs. Let G be a graph and x ∈ G a vertex, and let G be obtained from G by adding a vertex x and joining it to x and all the neighbours of x. We say that G is obtained from G by expanding the vertex x to an edge xx. Any graph obtained from a perfect graph by expanding a vertex is again perfect. Show that χ(H) ∈ {ω(H), ω(H) + 1} for every line graph H; Characterize the graphs whose line graphs are perfect.
29.09.2023 Scribe Note by Trishita Mukherjee
06.10.2023 Scribe Note by Sukanth E
11.10.2023 Scribe Note by Anirudh M
12.10.2023 Generating perfect graphs by extension at vertices with perfect graphs; alternate proof of the Wilf-Szekeres theorem; Some examples of Δ(G), χ(G) and χ(G) on K4, K5, K1, n.
13.10.2023 Discussion of the questions in Homework 3; revisiting the proof of the Wilf-Szekeres theorem and repetition of some vertex and edge coloring upper bounds.

Lecture Slides

Slides

Tutorials

Tutorial-1 - August 11, 2023

Homework

Homework-1- August 11, 2023

Homework-2- September 1, 2023

Homework-3- October 16, 2023

Class Tests

Two class tests will be conducted for this course.

Mid-semester exam

End-semester exam

Term Project (15%)

Midterm (25%)

Endterm (45%)

References

Additional references used