Skip to content
Preprint

Sharp quadratic $\chi$-binding functions for powers of bipartite graphs

Aug 2026 · 0 citations · 8 references
Mathematics

Abstract

For every natural number $r\geq 2$, we construct $r^{th}$ powers of bipartite graphs whose chromatic number is quadratic in their clique number, showing that the straightforward quadratic upper bound is best possible. We thereby settle an open problem posed by Chakraborty, Chandran, Jacob and Pillai [J. Graph Theory 112(3) (2026), 235-254] by establishing the sharpness of the quadratic bound for squares of bipartite graphs.

View source

Similar papers

Preprint Oct 2026

Positive discrepancy of graphs far from Tur\'an graphs

We prove that, for every $\eps>0$, any $n$-vertex graph that needs at least $\eps n^2$ edge changes to become a Tur\'an graph has positive discrepancy at least $c_\eps n^{5/4}$. Consequently, every such regular graph has second eigenvalue at least $c'_\eps n^{1/4}$. These results prove two conjectures of R\"aty, Sudako...

Le Xu, Bo Zhou · 1 citation · ⚡1
Preprint Oct 2026

A sharp upper bound on the number of spanning forests of regular graphs

Let $G$ be a simple graph on $n$ vertices, and let $F(G)$ denote the number of its spanning forests. Bencs and Csikv\'ari [Upper bound for the number of spanning forests of regular graphs, European J. Combin. 110 (2023) 103677] proved that every $r$-regular graph $G$ with $r\geq 2$ satisfies $F(G) \leq r^{n}$. They fur...

Ting-Zeng Wu, S. Lu, Xiang-Shuai Dong · 0 citations
Preprint Sep 2026

Logarithmic Circumference In Tough Graphs

For every real $t>0$, we prove that every $2$-connected $t$-tough graph contains a cycle of length at least $\ell$ whenever $n \leq \ell(1 + 1/t)^{\lfloor \ell/2\rfloor - 1}$. This establishes the logarithmic bound conjectured by Broersma, van den Heuvel, Jung, and Veldman.

Levi Segal, J. Verstraete · 1 citation
Preprint Sep 2026

Maximizing $K_r + I_r$ in graphs with fixed edge density

After the initial idea for the main proof was found by the authors, various AI models were used to streamline the argument and perform the calculations necessary for completion of the proof.

J'ozsef Balogh, Andrzej Grzesik, Bernard Lidický et al. · 0 citations
Preprint Sep 2026

Box-Delaunay graphs of large chromatic number

For every $n$, we construct a 2-dimensional $n$-element poset whose Hasse diagram has independence number $n\exp(-\Omega(\sqrt{\log n}))$, and consequently, chromatic number $\exp(\Omega(\sqrt{\log n}))$. This also yields an $n$-point planar set whose box-Delaunay graph satisfies the same bounds.

István Tomon · 1 citation
Preprint Sep 2026

When are random regular triangle-free graphs bipartite?

We study the structure of random $d$-regular triangle-free graphs and show that a sharp phase transition occurs at $d=\frac{\sqrt 3}{2}\sqrt{n \log n}$. For smaller $d$, asymptotically almost surely the graph is non-bipartite, whereas for greater $d$, asymptotically almost surely the graph is bipartite.

Gregory Decamillis, Gao Pu · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.