***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Date: Thursday 27th October, 3:00 in Fine Hall 224.
 
Speaker:  Vaidy Sivaraman (Binghampton)

Title: Three graph classes: mock threshold, cute, and nice graphs

Abstract: A graph class, defined in one way, can be characterized in
several other ways. Forbidden induced subgraphs, intersection of
subobjects, relationship among invariants, and vertex ordering are some of
the most common ways. A graph is mock threshold if every induced subgraph
of it has a vertex with degree or codegree at most 1.  I will present the
forbidden induced subgraph characterization for this class  due to Richard
Behr, Thomas Zaslavsky, and myself.  A graph is cute if every induced
cycle in it is a triangle or a  quadrilateral. We discuss chi-boundedness,
recognition and optimization for this class. A graph is nice if the
difference between the chromatic number and clique number is either 0 or 1
for every induced subgraph of it. Perfect graphs, planar graphs,
tripartite graphs, and line graphs are nice. We will address the following
question: Is there anything nice about nice graphs?

                       -----------

Next week: fall recess. Week after: Oliver Schaudt

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)