Discrete Geometry and Combinatorics Seminar

Vaidyanathan SivaramanSUNY at Binghamton
Mock-threshold graphs

Monday, April 14, 2014 - 2:30pm
Malott 206

Ever since the resolution of the Strong Perfect Graph Conjecture by Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, the subject of induced subgraphs has attracted the attention of several researchers. A graph is said to be a threshold graph if its vertices can be assigned weights (real numbers) such that there is an edge between two vertices if and only if the sum of their weights crosses a fixed threshold (another real number). There is a simple forbidden induced subgraph characterization of threshold graphs. We relax the definition of a threshold graph to get a bigger class, one we call the class of mock-threshold graphs. We will discuss their place with respect to other well-known classes of graphs, and aim for a forbidden induced subgraph characterization of mock-threshold graphs. This is joint work with Richard Behr and Thomas Zaslavsky.