Cliques in Squares of Graphs with Maximum Average Degree less than 4

Author name not available (Why is that?)

Abstract: Hocquard, Kim, and Pierron constructed, for every even integer

D g e 2

, a 2-degenerate graph

G_{D}

with maximum degree

D

such that

o m e g a (G_{D}^{2}) = f r a c 52 D

. They asked whether (a) there exists

D_{0}

such that every 2-degenerate graph

G

with maximum degree

D g e D_{0}

satisfies

c h i (G^{2}) l e f r a c 52 D

and (b) whether this result holds more generally for every graph

G

with mad(G)<4. In this direction, we prove upper bounds on the clique number

o m e g a (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

o m e g a (G^{2}) l e f r a c 52 D + 72

(with

o m e g a (G^{2}) l e f r a c 52 D + 60

when

D

is sufficiently large). And if

G

has mad(G)<4 and maximum degree

D

, then

o m e g a (G^{2}) l e f r a c 52 D + 532

. Thus, the construction of Hocquard et al. is essentially best possible.

No records found.

This page was built for publication: Cliques in Squares of Graphs with Maximum Average Degree less than 4