For every integer $k\ge2$, Chen and Raspaud conjectured that each graph $G$ with odd girth $\og(G)\ge2k+1$ and maximum average degree $\mad(G)<2+1/k$ has a $(2k+1:k)$-coloring. In this paper, we prove the conjecture.
Answering a question of Noga Alon, we generalize a result of Janzer and Yip to show that every $k$-edge-coloring of $K_{r^k+1}$ contains a monochromatic subgraph with chromatic number at least $r+1$ and diameter $O(k^{3/2}r^{k/2}\log r)$.
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.
A graph $G$ is said to be $k$-collapsible if $G$ has minimum degree $k$ and every non-null proper induced subgraph of $G$ has minimum degree less than $k.$ In 2018, Bickle conjectured that the minimum number of vertices of degree $k$ in a $k$-collapsible graph of order $n$ with $k\ge 3$ is ${\rm max}\{\lceil 2n/(2k-1)\...
For any $n$, there exists finite simple graphs $G$ and $H$ such that $\chi(G),\chi(H)>n$ and $\chi(G \times H) = 4$.
We construct a finite connected simple cubic graph $F$ such that every signing of its edges yields a signed adjacency matrix with an eigenvalue outside $[-2\sqrt2,2\sqrt2]$. This disproves the Bilu--Linial signing conjecture for general regular graphs. The graph $F$ is not Ramanujan, and the conjecture restricted to Ra...
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.
We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.
