For every odd integer $t\ge17$, we prove that an explicit circulant graph on $5t-10$ vertices is doubly saturated $R(3,t)$-good. The graph is triangle-free and has independence number $t-1$. Adding any nonedge creates a triangle, whereas deleting any edge creates an independent set of order $t$. This settles Conjecture 2 of Przybocki, Mackey, Heule, and Subercaseaux. A cyclic sumset identity and explicit witnesses prove the local saturation properties. Writing $t=2m+1$, a five-layer reduction proves the independence bound via a uniform affine certificate for $m\ge30$ and an exhaustive checker for $8\le m\le29$. The checker soundness and the complete argument are formalized in Lean 4.32.2. Consequently, $2t-1\le \operatorname{DS}(3,t)\le 5t-10$ for odd $t\ge17$.
For a graph $H$ with $3\mid e(H)$, the zero-sum Ramsey number $R(H,\Z_3)$ is the least integer $N$ such that every labeling of the edges of $K_N$ by elements of $\Z_3$ contains a copy of $H$ whose edge labels sum to zero. We determine the last previously unresolved infinite family in the complete-graph case modulo $3$. More precisely, we prove that \(R(K_n,\Z_3)=n+3\) for every $n\ge 10$ satisfying $n\equiv 1\pmod 3$. Consequently, for $k\ge 1$, \(R(K_{9k+7},\Z_3)=9k+10\), resolving a problem of Caro and Mifsud.
For $1\le s<t$ and any graph $G$, the weakened Gallai-Ramsey number $gr^t_s(G)$ is defined to be the least $p\in \mathbb{N}$ such that every Gallai $t$-coloring of the edges of $K_p$ (i.e., a $t$-coloring that lacks rainbow triangles) contains a subgraph isomorphic to $G$ whose edges use at most $s$ of the colors. In the case of a book graph $B_n:=K_2+nK_1$, Jakhar and Moun determined the values $gr^3_2(B_3)=6$ and $gr^3_2(B_4)=7$. In this paper, we extend their results to $t>3$ colors, and we determine the values of $gr^3_2(B_n)$ for $5\le n\le 15$. General lower bounds for $gr^t_2(B_n)$ are also given.
Albertson's conjecture asserts that every finite simple graph $G$ with $\chi(G) \ge r$ satisfies $\operatorname{cr}(G) \ge \operatorname{cr}(K_r)$. Building on Cranston's verification for $r \le 24$ and his reduction of $r \in \{25,26\}$ to three residual orders, we eliminate those residual cases and then prove the cases $r=27,28,29$. The first structural ingredient is a Kempe-chain construction: if a $k$-critical graph has a vertex of degree $k-1$, then it contains a branch-clean essential immersion of $K_k$. Essential immersions are crossing-monotone, so a critical counterexample must have minimum degree at least $k$. For $r=27$, this one-unit degree gain, Gallai's join structure, critical-graph edge bounds, and induced-subgraph averaging close every possible order. For $r=28$ and $r=29$, the remaining near-$2r$ orders are converted to dense complements. Stehl\'ik's coloring theorem makes the odd-order complements factor-critical; a clique-partition obstruction yields an anti-tight matching property; and Tutte barriers, Hall-type expansion, and deficit bookkeeping eliminate the final cases. At order 58 for $r=29$, Rabern's coloring inequality handles the regular case, while the last degree-deficit-two case is reduced to two disjoint triangles and a finite barrier analysis.
A famous conjecture of Erd\H{o}s and Hajnal (1969) states that for every integer $g\ge 4$ there is a smallest function $f_g:\mathbb{N}\to\mathbb{N}$ such that every graph of chromatic number at least $f_g(k)$ contains a subgraph of chromatic number $k$ and girth at least $g$. So far, this has only been proved for $g=4$ by R\"odl (1977), with $f_4(k)$ bounded by a tower of height $\Theta(k^2\log k)$. We exhibit a surprising connection between finding high-chromatic subgraphs of large odd-girth (avoiding short odd cycles) and lower-bounding multicolor Ramsey numbers of odd cycles. Using this connection, we prove that for every odd $g\ge 5$ there is a function $h_g:\mathbb{N}\to\mathbb{N}$ growing as a power tower of height $\frac{g-3}{2}$ such that every graph of chromatic number at least $h_g(k)$ contains a subgraph of chromatic number at least $k$ and odd-girth at least $g$. This proves a conjecture of Mohar and Wu (2018), addresses a question of Erd\H{o}s and Hajnal (1975), and for $g=5$ improves R\"odl's bound on $f_4(k)$ to a single-exponential. We extend this to a much more general meta-theorem which applies to many graph parameters: if $f$ is the fractional chromatic number, the Hall ratio, or the strict vector chromatic number (Lov\'{a}sz-Theta-function of the complement), then for every $k,g\in\mathbb{N}$, every graph $G$ with sufficiently large $f(G)$ contains a subgraph $G'$ of odd-girth at least $g$ with $f(G')\ge k$. The key Ramsey-theoretic ingredient is a new lower bound on Ramsey numbers of odd cycles. For $p\ge 1$, let $\mathcal{O}_p=\{C_3,C_5,\ldots,C_{2p+1}\}$. We show that $R_k(\mathcal{O}_p)\ge(\log^{(p-1)}k)^{k/3-o(k)}$ for every fixed $p$, where $\log^{(p-1)}$ denotes the $(p-1)$-fold iterated logarithm. This yields the first superexponential lower bound on multicolor Ramsey numbers of fixed odd cycles, and extends the recent breakthrough by OpenAI for triangles.
For graphs $G$ and $H$, let $\mathbf N(G,H)$ denote the number of unlabeled, not necessarily induced copies of $H$ in $G$, and let $\mathbf N_{\mathcal P}(n,H)$ be the maximum of $\mathbf N(G,H)$ over all $n$-vertex planar graphs $G$. We prove that, for every fixed integer $m\geq 3$, $$\mathbf N_{\mathcal P}(n,C_{2m+1})=2m\left(\frac{n}{m}\right)^m+O_m\!\left(n^{m-1/5}\right).$$ The proof uses a sharp weighted cycle--path inequality for edge probability measures on finite complete graphs. This strengthens a conjecture of Heath, Martin, and Wells and, together with their reduction lemma, yields the stated asymptotic formula.
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)}\le F(N)<\sqrt{6N}$. The lower bound raises the finite-order scale supplied by the Cameron-Clow path-colour construction from $\log N/\log\log N$ to a fixed power of $N$. Its proof constructs a palette-code graph from a binary covering code $\mathcal{C}\subseteq\{0,1\}^p$ and establishes the exact identities $\chi(G)=2p+\ell-\rho(\mathcal{C})$ and $\psi(G)=2p$. Near-middle Hamming coverings yield the exponent $1/6$. The upper bound combines Polavarapu's connectivity theorem, the Chvatal-Erdos Hamiltonicity theorem, and maximum-independent-set stripping.
Shuyan Chen· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
