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{5}{2}D$.  We prove for (a) all 2-degenerate graphs $G$ and (b) all graphs $G$ with $\text{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{5}{2}D+72$.  And if $G$ has $\text{mad}(G)<4$ and maximum degree $D$, then $\omega (G^2)\le \frac{5}{2}D+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