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

-

## Locations

Online event

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

## Event Contact

Co-Director, M.S. in Computational Decision Science and Operations Research (CDSOR) Associate Professor of Applied Mathematics
312.567.3128