The linear list Hadwiger conjecture asserts that every $K_t$-minor-free graph is $O(t)$-choosable. Following an approach outlined by Delcourt and Postle, we recently established $O(t\log\log t)$-choosability. Soon afterward, OpenAI provided a proof of the conjecture. A key new ingredient of their proof is a linear boun...
Let $\lambda=\{k_1,\ldots,k_q\}$ be a partition, and let $|\lambda|=k_1+\cdots+k_q$. A $|\lambda|$-list assignment $L$ of a graph $G$ is a $\lambda$-assignment if its color set can be partitioned into $q$ disjoint sets $X_1,\ldots,X_q$ such that $|L(v)\cap X_i|=k_i$ for every vertex $v$ and every $i\in[q]$. This notion...
Let $f(n,t)$ be the minimum number of triangles in a tripartite graph with $n$ vertices in each part and minimum degree at least $n+t$. In 1975, Bollob\'{a}s, Erd\H{o}s and Szemer\'{e}di proved that $f(n,1)=\min\{4,n\}$. They further remarked that it is ``very likely''that $f(n,t)\ge4t^3$ for $n\ge5t$. They also proved...
Let $G$ be a $3$-partite graph with $k$ vertices in each part such that the bipartite graph induced by any two parts contains no cycle of length four. Fischer and Matou\v{s}ek [J. Combin. Theory Ser. A, 2001] asked for the maximum number of triangles in such a graph. They obtained the lower bound $(1-o(1))k^{3/2}$ and...
Chun-Qiu Fang, Rong-Xing Xu· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.