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

-
Vaidy Sivaraman , Binghamton University
Fine Hall 224

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?