Let $G$ be the line graph of a finite simple graph, with $n\geq1$ vertices and maximum degree $\Delta$. We prove that single-site Glauber dynamics for uniform proper $q$-colorings mixes in $O_\Delta(n\log(n/\varepsilon))$ steps for every integer $q\geq\Delta+5$. Our proof uses the Bochner framework of Chen and Liu (2026).
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 prove that, for every integer $k\ge 2$, there exists a constant $c_k>0$ such that every graph on $n\ge R(k,k)$ vertices with maximum degree $\Delta$ contains an induced subgraph on at least $n-c_k\sqrt{\Delta}$ vertices whose maximum degree is attained by at least $k$ vertices. This confirms a conjecture of Caro and...
Let $G$ be a finite simple graph and let $S\subseteq V(G)$. We prove that the minimum number of vertices meeting every cycle that intersects $S$ is at most the maximum number of vertices of $S$ covered by a collection of vertex-disjoint cycles. This answers a question posed by Bowler, Ghorbani, Gut, Jacobs, and Reich [...
Let $G$ be a graph. Under a strong edge coloring of $G$, every color class is an induced matching. The strong chromatic index of $G$, denoted by $\chi'_s(G)$, is the smallest integer $k$ such that $G$ admits a strong edge coloring with $k$ colors. Denote by $\Delta(G)$ the maximum degree of $G$. In this paper, we prove...
We prove that each $2$-edge-coloured spanning subgraph $G$ of $K_{n,n}$ with $\delta(G)\ge \lfloor (2n+1)/3 \rfloor$ can be covered by at most three monochromatic components. We provide a $2$-edge-coloured spanning subgraph of $K_{n,n}$ showing this minimum degree condition is sharp.
César Bispo, George Kontogeorgiou, M. Lage et al.· 0 citations
We extend the conjecture of Erd\H{o}s and Gy\'arf\'as on monochromatic path covers to the setting of monochromatic cycle covers. We prove that, for all $n$, every 2-edge-coloring of the complete graph on $n$ vertices contains a collection of at most $\lceil\sqrt{n}\rceil$ monochromatic cycles, all of the same color, th...
