More Like this

1. Spanning Weakly Even Trees of Graphs

   https://doi.org/10.1002/jgt.70041  

   Ai, Jiangdong; Ellingham, M N; Gao, Zhipeng; Huang, Yixuan; Liu, Xiangzhou; Shan, Songling; Špacapan, Simon; Yue, Jun (August 2026, Journal of Graph Theory)

   ABSTRACT Let be a graph (with multiple edges allowed) and let be a tree in . We say that isevenif every leaf of belongs to the same part of the bipartition of , and that isweakly evenif every leaf of that has maximum degree in belongs to the same part of the bipartition of . We confirm two recent conjectures of Jackson and Yoshimoto by showing that every connected graph that is not a regular bipartite graph has a spanning weakly even tree. 

   more » « less
2. Sharp lower bounds for the number of maximum matchings in bipartite multigraphs

   https://doi.org/10.1002/jgt.23080  

   Kostochka, Alexandr V; West, Douglas B; Xiang, Zimu (July 2024, Journal of Graph Theory)

   Abstract We study the minimum number of maximum matchings in a bipartite multigraph with parts and under various conditions, refining the well‐known lower bound due to M. Hall. When , every vertex in has degree at least , and every vertex in has at least distinct neighbors, the minimum is when and is when . When every vertex has at least two neighbors and , the minimum is , where . We also determine the minimum number of maximum matchings in several other situations. We provide a variety of sharpness constructions. 

   more » « less
3. Local version of Vizing's theorem for multigraphs

   https://doi.org/10.1002/jgt.23155  

   Conley, Clinton T; Grebík, Jan; Pikhurko, Oleg (July 2024, Journal of Graph Theory)

   Abstract Extending a result of Christiansen, we prove that every multigraph admits a proper edge colouring which islocal, that is, for every edge with end‐points , where (resp. ) denotes the degree of a vertex (resp. the maximum edge multiplicity at ). This is derived from a local version of the Fan Equation. 

   more » « less
4. Asymptotically Optimal Proper Conflict‐Free Coloring

   https://doi.org/10.1002/rsa.21285  

   Liu, Chun‐Hung; Reed, Bruce (May 2025, Random Structures & Algorithms)

   ABSTRACT A proper conflict‐free coloring of a graph is a coloring of the vertices such that any two adjacent vertices receive different colors, and for every non‐isolated vertex , some color appears exactly once on the neighborhood of . Caro, Petruševski and Škrekovski conjectured that every connected graph with maximum degree has a proper conflict‐free coloring with at most colors. This conjecture holds for and remains open for . In this article we prove that this conjecture holds asymptotically; namely, every graph with maximum degree has a proper conflict‐free coloring with colors. 

   more » « less
5. Infinite stationary measures of co‐compact group actions

   https://doi.org/10.1112/blms.70198  

   Alhalimi, Mohammedsaid; Hutchcroft, Tom; Pan, Minghao; Tamuz, Omer; Zheng, Tianyi (December 2025, Bulletin of the London Mathematical Society)

   Abstract Let be a finitely generated group, and let be a nondegenerate, finitely supported probability measure on . We show that every co‐compact action on a locally compact Hausdorff space admits a nonzero ‐stationary Radon measure. The main ingredient of the proof is a stationary analog of Tarski's theorem: we show that for every nonempty subset there is a ‐stationary, finitely additive measure on that assigns unit mass to . 

   more » « less