


























Wegner conjectured that if $G$ is a planar graph with maximum degree $Δ\ge 8$, then $χ(G^2)\le \left\lfloor \frac32Δ\right\rfloor +1$. This problem has received much attention, but remains open for all $Δ\ge 8$. Here we prove an analogous bound on $ω(G^2)$: If $G$ is a plane graph with $Δ(G)\ge 36$, then $ω(G^2)\le \lfloor\frac32Δ(G)\rfloor+1$. In fact, this is a corollary of the following lemma, which is our main result. If $G$ is a plane graph with $Δ(G)\ge 19$ and $S$ is a maximal clique in $G^2$ with $|S|\ge Δ(G)+20$, then there exist $x,y,z\in V(G)$ such that $S=\{w:|N[w]\cap\{x,y,z\}|\ge 2\}$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。