For every fixed $k\ge 3$, every finite nonempty clutter $\mathcal{H}$ can be realized exactly as the family of inclusion-minimal terminal traces of the $k$-bad odd cycles, namely the odd cycles $C$ satisfying $\chi(G[V(C)])\ge k+1$. The host graph $G$ may be chosen $2$-connected, with $T=V(\mathcal{H})$ independent, an...
We prove that there is an absolute constant $c>0$ such that every graph of chromatic number at least $r$ and at most $cr^3\log^2 r$ edges contains at least $\binom r3$ triangles. The proof has three ingredients. First, a sparse-core argument based on a triangle-sensitive coloring estimate of Harris extracts, from any c...
Conlon and Lee asked for strongly dominating graphs beyond norming graphs and even paths. We construct a two-parameter family of pairwise non-isomorphic $2$-connected strongly dominating graphs that are not seminorming, and hence lie outside the two classes of examples previously identified for signed strong domination...
For a graph $G$, let $\psi(G)=\max\{\chi(G[V(C)]):C$ is an odd cycle of $G\}$, with $\psi(G)=0$ when $G$ is bipartite. For positive integers $N$, set $F(N)=\max\{\chi(G)-\psi(G):|V(G)|\le N\}$. The function $F$ measures the finite-order additive gap arising from an open problem of Erdos and Hajnal. We prove $N^{1/6-o(1...
Shu-Yan Chen· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.