Dan Cranston

Overlap Number of Graphs

Abstract: An overlap representation of a graph G assigns set to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The overlap number φ(G) is the minimum size of the union of the sets in such a representation. In this talk, we determine the maximum value of φ(G) over all n-vertex planar graphs and also over all general n-vertex graphs. This is joint work with Nitish Korula, Timothy LeSaulnier, Kevin Milans, Christopher Stocker, Jennifer Vandenbussche, and Douglas B. West.