Lecture 1, February 16th: 
Introduction: Basic
graph concepts, intersection graphs, interval
graphs sneak preview. Examples of some real life applications of special
graph classes.
Lecture 2, February 23: Perfect
Graphs: Lovasz perfect graphs theorem. p-critical graphs. The strong
perfect graph conjecture.
Lecture 3, March 2nd: Chordal
graphs: Fulkerson-Gross, Dirac Thms. Tarjan-Yannakakis MCS algorithm
for generating a perfect elimination order. Linear algorithm to test if
a vertex order is a PEO. Chordal graphs as intersection graphs.
Lecture 4, March 9th: Chordal graphs and evolutionary trees. The Minimum Fill In Problem. Relation to sparse matrix factorization. Yannakakis proof that Minimum Fill In is NP-complete.
Lecture 5, March 16th: Chordal graphs are perfect. Computing the chromatic number and all maximal cliques in a chordal graph. Computing the stability number and a clique partition. Parameterized analysis of the Minimum Fill In Problem: Two algorithms showing the problem is fixed parameter tractable (Kaplan, Shamir, Tarjan)
Lecture 6, March 30th: Comparability
Graphs: implication classes and Gamma-chains. Uniquely Partially
Orderable graphs, Shevrin-Filipov theorem. G-decomposition and characterizations.
Lecture 7, April 6th: Comparability graph characterization Theorem. Two polynomial recognition algorithms. Some optimization algorithms. Partial order dimension. Dushnik-Miller Theorem.
Lecture 8, April 13th:Comparability
invariants. Interval
Graphs: Gilmore-Hoffman Theorem.Lekkerkerekr-Boland Theorem (w/o
proof) . Preference and Indifference: semiorder, Roberts' theorem, unit
and proper interval graphs.
Lecture 9, May 4th:
Interval graph recognition: Ramalingan-Pandu Rangan algorithm;
The consecutive ones problem (C1P) and Physical mapping of DNA;
Booth-Leuker PQ-trees linear algorithm for C1P and interval graph
recognition.
Extensions of C1P; interval number; circular ones property.
Lecture 10, May 18th
(guest speaker: Martin
C. Golumbic):
Circle graphs and overlap graphs; Function graphs;
Golumbic-Rotem-Urrtia characterization theorem.
Strong Matchings; Polynomiality on cocomparability graphs
(Golumbic-Loewnstein 97)
Trapezoid Graphs: Dagan-Golumbic-Pinter characterization theorem;
open problems.
Lecture 11, May 25th
Interval graph applications:
Interval graph models in temporal reasoning,
constrained interval graphs and interval sandwich problems (Golumbic
Shamir 93). Other sandwich problems.
Treewidth, pathwidth, bandwidth, and their connections to
interval and unit interval graphs (Kaplan Shamir 96)
Lecture 12, June 1st:
Instersection Graphs:
Every graph is an intersection graph; Intersection classes.
Injective interscetions classes.
Scheinerman's characterization for intersection classes of graphs;
Line graphs: properties and characterizations.
Material Planned but Not covered this time:
Other
Graph Families: split graphs ; threshold graphs ; Circular
arc Graphs ; perfect elimination bipartite graphs.
chordal bipartite graphs. Greedily solvable network flow problems. ATF
graphs.
Bibliography
main reference: M. C. Golumbic. Algorithmic Graph
Theory and Perfect Graphs . Academic Press, New York, 1980.
C. Berge. Graphs and Hypergraphs . North-Holland,
Amsterdam, 1973.
S. Even. Graph Algorithms. Computer Science Press,
Rockville, Maryland, 1979.
P. Fishburn. Interval Orders and Interval Graphs.
Wiley, New York, 1985.
M. R. Garey and D. S. Johnson. Computers and Intractability:
A Guide to the Theory of NP-Completeness. W. H. Freeman and co., San Francisco,
1979.
G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial
Optimization . Wiley, New York, 1988.
Ch. Papadimitriou and K. Steiglitz. Combinatorial
Optimization: Algorithms and Complexity . Prentice-Hall, Englewood
Cliffs, New Jersey, 1982.
F. S. Roberts. Discrete Mathematical Models, with
Applications to Social Biological and Environmental Problems. Prentice-Hall,
Englewood Cliffs, New Jersey, 1976.
D. B. West. The Art oc Combinatorics: Volume
I: Extermal Graph Theory. (manuscript, Fall 1996)
Please send comments to: Ron
Shamir. email: shamir@math.tau.ac.il
(guest speaker: Martin
C. Golumbic):
Circle graphs and overlap graphs; Function graphs;
Golumbic-Rotem-Urrtia characterization theorem. Strong Matchings; Polynomiality on cocomparability graphs (Golumbic-Loewnstein 97)
Trapezoid Graphs: Dagan-Golumbic-Pinter characterization theorem; open problems.
Lecture 11, May 25th
Interval graph applications:
Interval graph models in temporal reasoning,
constrained interval graphs and interval sandwich problems (Golumbic
Shamir 93). Other sandwich problems.
Treewidth, pathwidth, bandwidth, and their connections to
interval and unit interval graphs (Kaplan Shamir 96)
Lecture 12, June 1st:
Instersection Graphs:
Every graph is an intersection graph; Intersection classes.
Injective interscetions classes.
Scheinerman's characterization for intersection classes of graphs;
Line graphs: properties and characterizations.
Material Planned but Not covered this time:
Other
Graph Families: split graphs ; threshold graphs ; Circular
arc Graphs ; perfect elimination bipartite graphs.
chordal bipartite graphs. Greedily solvable network flow problems. ATF
graphs.
Bibliography
main reference: M. C. Golumbic. Algorithmic Graph
Theory and Perfect Graphs . Academic Press, New York, 1980.
C. Berge. Graphs and Hypergraphs . North-Holland,
Amsterdam, 1973.
S. Even. Graph Algorithms. Computer Science Press,
Rockville, Maryland, 1979.
P. Fishburn. Interval Orders and Interval Graphs.
Wiley, New York, 1985.
M. R. Garey and D. S. Johnson. Computers and Intractability:
A Guide to the Theory of NP-Completeness. W. H. Freeman and co., San Francisco,
1979.
G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial
Optimization . Wiley, New York, 1988.
Ch. Papadimitriou and K. Steiglitz. Combinatorial
Optimization: Algorithms and Complexity . Prentice-Hall, Englewood
Cliffs, New Jersey, 1982.
F. S. Roberts. Discrete Mathematical Models, with
Applications to Social Biological and Environmental Problems. Prentice-Hall,
Englewood Cliffs, New Jersey, 1976.
D. B. West. The Art oc Combinatorics: Volume
I: Extermal Graph Theory. (manuscript, Fall 1996)
Please send comments to: Ron
Shamir. email: shamir@math.tau.ac.il
Other
Graph Families: split graphs ; threshold graphs ; Circular
arc Graphs ; perfect elimination bipartite graphs.
chordal bipartite graphs. Greedily solvable network flow problems. ATF
graphs.
Bibliography
main reference: M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs . Academic Press, New York, 1980.
C. Berge. Graphs and Hypergraphs . North-Holland, Amsterdam, 1973.
S. Even. Graph Algorithms. Computer Science Press, Rockville, Maryland, 1979.
P. Fishburn. Interval Orders and Interval Graphs. Wiley, New York, 1985.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and co., San Francisco, 1979.
G. L. Nemhauser and L. A. Wolsey. Integer and Combinatorial Optimization . Wiley, New York, 1988.
Ch. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity . Prentice-Hall, Englewood Cliffs, New Jersey, 1982.
F. S. Roberts. Discrete Mathematical Models, with Applications to Social Biological and Environmental Problems. Prentice-Hall, Englewood Cliffs, New Jersey, 1976.
D. B. West. The Art oc Combinatorics: Volume I: Extermal Graph Theory. (manuscript, Fall 1996)
Please send comments to: Ron Shamir. email: shamir@math.tau.ac.il