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.
Let $F_2(C_n)$ be the $2$-token graph of the cycle $C_n$ and let $\rho$ denote the packing number. G\'omez Soto and R\'ios-Castro recently proved that $\rho(F_2(C_n))\ge a(n)$ for $n\ge 19$, where $a(n)$ is an explicit expression. In this note, we prove that \[ \rho(F_2(C_n))\ \ge\ \left\lfloor\frac{n(n-2)}{10}\right\r...
For a simple graph $G$ with $n$ vertices, write its chromatic polynomial in the rising factorial basis as $$ \chi_G(x)=\sum_{i=0}^{n}(-1)^{n-i}c_i(G)\langle x\rangle_i,$$ where $ \langle x\rangle_i=x(x+1)\cdots(x+i-1).$ The associated $\tau$-polynomial $$ \tau_G(x)=\sum_{i=0}^{n}c_i(G)x^i $$ was defined and systematica...
Ming-Yang Kang, Zhi-Xin Liu, Sophie C. C. Sun et al.· 0 citations
Let $G$ be a simple graph with cover ideal $J(G)$ in a polynomial ring $S = \k[x_1, \ldots, x_n]$. For each integer $t \ge 1$, let $\alpha_t(G)$ denote the maximum size of an ordered matching $M$ of $G$ with alternating path length $\ell(M) \le 2t - 1$. Hang, Tam, and Vu established that \[ \operatorname{depth}\!\left(...
In this paper we prove that every graph $G$ with no induced six-vertex path satisfies $\chi(G)\le \omega(G)^{c\log_2\omega(G)}$ for $c=45/\log_2(4/3)<109$. The best previous bound was exponential in $\omega(G)$. Our result is the first quasi-polynomial bound for $P_6$-free graphs and generalizes the bound for $P_5$-fre...
Let $P_t$ denote the induced path on $t$ vertices. Let $\omega(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gy\'arf\'as (1987) proved that every $P_t$-free graph $G$ satisfies $\chi(G)\le(t-1)^{\omega(G)-1}$, and Gravier, Ho\`ang, and Maffray (2003) improved this to $\chi(G)\le (t-2)^{\omega(G)...
We prove that, for every $k\ge2$ and every sufficiently large odd $n$, the induced size--Ramsey number of $C_n$ satisfies \[ \widehat R_{\mathrm{ind}}(C_n;k)=e^{\Theta(k)}n. \] This improves the previous upper bound of $e^{O(k\log k)}n$ and resolves a conjecture of Brada\v{c}, Dragani\'c and Sudakov. We obtain this res...
Lan Wang, Xiao-Lin Wang· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.