More Like this

1. A Note on Directed Analogues of the Sidorenko and Forcing Conjectures

   https://doi.org/10.37236/11675  

   Fox, Jacob; Himwich, Zoe; Mani, Nitya; Zhou, Yunkun (July 2025, The Electronic Journal of Combinatorics)

   We study analogues of Sidorenko’s conjecture and the forcing conjecture in oriented graphs, showing that natural variants of these conjectures in directed graphs are equivalent to the asymmetric, undirected analogues of the conjectures. 

   more » « less
2. Longest cycles in vertex‐transitive and highly connected graphs

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

   Groenland, Carla; Longbrake, Sean; Steiner, Raphael; Turcotte, Jérémie; Yepremyan, Liana (July 2025, Bulletin of the London Mathematical Society)

   Abstract We present progress on three old conjectures about longest paths and cycles in graphs. The first pair of conjectures, due to Lovász from 1969 and Thomassen from 1978, respectively, states that all connected vertex‐transitive graphs contain a Hamiltonian path, and that all sufficiently large such graphs even contain a Hamiltonian cycle. The third conjecture, due to Smith from 1984, states that for in every ‐connected graph any two longest cycles intersect in at least vertices. In this paper, we prove a new lemma about the intersection of longest cycles in a graph, which can be used to improve the best known bounds toward all the aforementioned conjectures: First, we show that every connected vertex‐transitive graph on vertices contains a cycle (and hence path) of length at least , improving on from DeVos [arXiv:2302:04255, 2023]. Second, we show that in every ‐connected graph with , any two longest cycles meet in at least vertices, improving on from Chen, Faudree, and Gould [J. Combin. Theory, Ser. B,72(1998) no. 1, 143–149]. Our proof combines combinatorial arguments, computer search, and linear programming. 

   more » « less
3. Towards the Small Quasi-Kernel Conjecture

   https://doi.org/10.37236/11043  

   Kostochka, Alexandr V.; Luo, Ruth; Shan, Songling (July 2022, The Electronic Journal of Combinatorics)

   Let $D=(V,A)$ be a digraph. A vertex set $$K\subseteq V$$ is a quasi-kernel of $$D$$ if $$K$$ is an independent set in $$D$$ and for every vertex $$v\in V\setminus K$$, $$v$$ is at most distance 2 from $$K$$. In 1974, Chvátal and Lovász proved that every digraph has a quasi-kernel. P. L. Erdős and L. A. Székely in 1976 conjectured that if every vertex of $$D$$ has a positive indegree, then $$D$$ has a quasi-kernel of size at most $|V|/2$. This conjecture is only confirmed for narrow classes of digraphs, such as semicomplete multipartite, quasi-transitive, or locally semicomplete digraphs. In this note, we state a similar conjecture for all digraphs, show that the two conjectures are equivalent, and prove that both conjectures hold for a class of digraphs containing all orientations of 4-colorable graphs (in particular, of all planar graphs). 

   more » « less
4. Robertson’s conjecture and universal finite generation in the homology of graph braid groups

   https://doi.org/10.1007/s00029-024-00971-1  

   Knudsen, Ben; Ramos, Eric (November 2024, Selecta Mathematica)

   Abstract We formulate a categorification of Robertson’s conjecture analogous to the categorical graph minor conjecture of Miyata–Proudfoot–Ramos. We show that these conjectures imply the existence of a finite list of atomic graphs generating the homology of configuration spaces of graphs—in fixed degree, with a fixed number of particles, under topological embeddings. We explain how the simplest case of our conjecture follows from work of Barter and Proudfoot–Ramos, implying that the category of cographs is Noetherian, a result of potential independent interest. 

   more » « less
5. Decreasing the mean subtree order by adding k edges

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

   Cambie, Stijn; Chen, Guantao; Hao, Yanli; Tokar, Nizamettin (March 2024, Journal of Graph Theory)

   Abstract Themean subtree orderof a given graph , denoted , is the average number of vertices in a subtree of . Let be a connected graph. Chin et al. conjectured that if is a proper spanning supergraph of , then . Cameron and Mol disproved this conjecture by showing that there are infinitely many pairs of graphs and with , and such that . They also conjectured that for every positive integer , there exists a pair of graphs and with , , and such that . Furthermore, they proposed that provided . In this note, we confirm these two conjectures. 

   more » « less