On a problem of Sivaraman and a problem of Gy\'arf\'as
이 뉴스, 어떠셨어요?
한 번의 탭으로 반응을 남겨요 · 로그인 불필요
Abstract
The \textit{girth} of a graph $G$, denoted $\mathrm{g}(G)$, is the length of a shortest cycle in $G$.
If $G$ contains no cycle, we define $\mathrm{g}(G)=\infty$.
Sivaraman (2020) asked for the optimal $\chi$-bounding function for the class of graphs whose complements have girth at least $6$.
Let \(F(s) = \max\{\chi(G): \omega(G)\le s,\ \mathrm{g}(\overline{G})\ge 6\}\).
We prove that there exists a constant \(c>0\) such that
\[
c\left(\frac{s}{\log s}\right)^{4/3}
\le
F(s)
\le
(1+o(1))\frac{s^{3/2}}{\log s}.
\]
For small values, we establish the exact results
\[
F(1)=1,\; F(2)=2,\; F(3)=4,\; F(4)=5,\; F(5)=6,\; F(6)=8,
\]
and each bound is sharp.
A graph $G$ is \emph{almost perfect} if every induced subgraph $H$ of $G$ satisfies
\(\alpha(H)\omega(H)+1\ge |V(H)|\).
Gyárfás (2023) asked whether almost perfect graphs are $\chi$-bounded by the function $g(x)=x+1$.
We answer this question in the negative by showing that there is no constant $c$ such that every almost perfect
graph $G$ satisfies $\chi(G)\le \omega(G)+c$.