A note on 3‐partite graphs without 4‐cycles

Let $C_4$ be a cycle of order 4. Write $ex\left(n,n,n,C_4\right)$ for the maximum number of edges in a balanced 3‐partite graph whose vertex set consists of three parts, each has $n$ vertices that have no subgraph isomorphic to $C_4$. In this paper, we show that $ex\left(n,n,n,C_4\right)\ge \frac{3}{2}n\left(p+1\right)$, where $n=\frac{p\left(p?1\right)}{2}$ and $p$ is a prime number. Note that $ex\left(n,n,n,C_4\right)\le \left(\frac{3\sqrt{2}}{2}+o\left(1\right)\right)n^{\frac{3}{2}}$ from Tait and Timmons's works. Since for every integer $m$, one can find a prime $p$ such that $m\le p\le \left(1+o\left(1\right)\right)m$, we obtain that $\underset{n\to \infty }{\lim }\frac{ex\left(n,n,n,C_4\right)}{\frac{3\sqrt{2}}{2}{n}^{\frac{3}{2}}}=1$.     

On coloring numbers of graph powers

The weak $r$-coloring numbers ${\mathrm{wcol}}_r\left(G\right)$ of a graph $G$ were introduced by the first two authors as a generalization of the usual coloring number $\mathrm{col}\left(G\right)$, and have since found interesting theoretical and algorithmic applications. This has motivated researchers to establish strong bounds on these parameters for various classes of graphs.Let $G^p$ denote the $p$th power of $G$. We show that, all integers $p>0$ and $\Delta \ge 3$ and graphs $G$ with $\Delta \left(G\right)\le \Delta$ satisfy $\mathrm{col}\left(G^p\right)\in O\left(p\cdot {\mathrm{wcol}}_{\lceil p∕2\rceil }\left(G\right){(\Delta -1)}^{\lfloor p∕2\rfloor }\right)$; for fixed tree width or fixed genus the ratio between this upper bound and worst case lower bounds is polynomial in $p$. For the square of graphs $G$, we also show that, if the maximum average degree $2k-2<\mathrm{mad}\left(G\right)\le 2k$, then $\mathrm{col}\left(G^2\right)\le (2k-1)\Delta \left(G\right)+2k+1$.