We prove that every triangle-free graph with minimum degree at least $\frac{n}{3}$ is $4$-colorable and thereby settle a problem of Brandt and Thomass\'e (2005) at the threshold $\frac{n}{3}$. The number four is best possible. For a positive integer-valued function $f(n)=o(n)$, we relate the chromatic number of $f(n)$-...
For positive integers with , a circular ‐flow of a graph is defined as a pair where represents an orientation of , and is a function mapping the edges of to the set such that, at each vertex, the sum of the ‐values of the incoming edges equals the sum of the ‐values of the outgoing edges. The flow index of , denoted...
Jia-Ao Li, Xin-Yuan Li· Journal of Graph Theory· 0 citations
A B-coloring of a graph $G$ is a proper edge-coloring in which every $4$-cycle is rainbow. Let $q_B(G)$ be the minimum number of colors in such a coloring. Gy\'arf\'as and S\'ark\"ozy (2023) determine $q_B(G)$ when $G=P_m\square P_n$ is a rectangular grid. In this paper, we completely determine $q_B(G)$ for cylindrical...
In 2016, Reiher's clique density theorem determined the minimum number of copies of $K_t$ in a graph with a prescribed edge density. In this paper, we investigate its local version and prove a local clique density theorem in $H$-free graphs as follows. For integers $r$ and $t$ with $2\leq t\leq r-1$, any $r$-chromatic...
Jiaao Li, Xinyu Li, Yan Wang et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
