Discrete Applied Math Seminar by Dan Cranston: Cliques in Squares of Graphs with Maximum Average Degree Less Than 4

Speaker:

Dan Cranston, associate professor of computer science, Virginia Commonwealth University

Title: Cliques in Squares of Graphs with Maximum Average Degree Less Than 4

Abstract: Hocquard, Kim, and Pierron constructed, for every even integer \(D \ge 2\), a 2-degenerate graph \(G_D\) with maximum degree \(D\) such that \(\omega(G_D^2) = \frac 52D\).  We prove for (a) all 2-degenerate graphs \(G\) and (b) all graphs \(G\) with \(\mad(G) < 4\), upper bounds on the clique number \(\omega(G^2)\) of \(G^2\) that match the lower bound given by this construction, up to small additive constants.  We show that if \(G\) is 2-degenerate with maximum degree \(D\), then \(\omega(G^2) \le \frac 52D+72\).  And if \(G\) has \(\mad(G) < 4\) and maximum degree \(D\), then \(\omega(G^2) \le \frac 52D+532\). Thus, the construction of Hocquard et al. is essentially best possible.

This is joint work with Gexin Yu.

 

Discrete Applied Math Seminar

Request Zoom Link