Lecture #1: Introduction to Graph Theory
- Basic Definitions and Notations
- Intersection Graphs
- Circular-arc Graphs
- Interval Graphs
- Line graphs of bipartite graphs
Lecture #2: Perfect Graphs
- Definition of perfect graph
- Some Definitions and Properties
- Perfect Graph Theorem
Lecture #3: Perfect and Triangulated Graphs
- Perfect Graphs
- $p$-Critical Graphs
- A Polyhedral Characterization of Perfect Graphs
- The Strong Perfect Graph Conjecture
- Triangulated Graphs
- Introduction
- Characterizing Triangulated Graphs
- Recognizing Triangulated Graphs
- Time Complexity
Lecture #4: Recognizing Triangulated Graphs
- Recognizing Triangulated Graphs
- Generating a PEO
- Testing an Elimination Scheme
- Naive Algorithm
- Efficient Algorithm
- Example
- Correctness of the Algorithm
- Complexity of the Algorithm
- Triangulated Graphs as Intersection Graphs
- Evolutionary Trees
- Triangulated Graphs as Intersection Graphs
Lecture #5: Triangulated Graphs Are Perfect
- Triangulated Graphs Are Perfect
- Proving This Property
- Other Results
- Computing the Minimum Fill In
- The Problem
- Fill In is NP-Hard
- Chain Graphs
- Optimal Linear Arrangement (OLA)
- Chain Graph Completion (CGC)
- The result for Fill in
- Problems
Lecture #6: Algorithms for triangulated graphs and comparability graphs
- Some Optimization Algorithms on Triangulated Graphs
- Computing the chromatic number and all maximal cliques
- Finding $\alpha $ and $k$
- Comparability Graphs
- Some Definitions
- Implication Classes
- The Triangle Lemma
- Decomposition of Graphs
Lecture #7: Uniquely Partially Orderable Graphs
- Uniquely Partially Orderable Graphs
- Characterizations and Recognition Algorithms
Lecture #8: Some interesting graph families characterized by intersection
- Introduction
- Permutation graphs
- $F$-Graphs
- ``The air controllers strike''
- A composition of permutation diagram.
- Tolerance graphs
- Interval graphs as a subset of tolerance graphs.
- Bounded and unbounded tolerance graphs.
Lecture #9: Comparability Graphs
- Comparability Graph Recognition
- The Complexity of Comparability Graph Recognition
- Implementation
- Complexity Analysis
- Coloring and Other Problems on Comparability Graphs
- Comparability Graphs Are Perfect
- Maximum Weighted Clique
- Calculating $\alpha (G)$
- The Dimension of Partial Orders
Lecture #10: Comparability invariants and Interval Graphs
- Comparability invariants
- Interval graphs
Lecture #11: Interval Graphs
- Preference and Indifference
- Recognizing interval graphs
- A quadratic algorithm 1
- A Linear Algorithm
- More about the consecutive 1's property
Lecture #12: Temporal Reasoning
- Temporal Reasoning and Interval algebras
- Interval satisfiability problems
- Interval sandwich problems and ISAT
- A linear time algorithm for ISAT($\Delta _1}$)
- Bandwidth, Pathwidth and Proper Pathwidth
