An official website of the United States government
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
This content will become publicly available on July 4, 2026
A Note on Directed Analogues of the Sidorenko and Forcing Conjectures
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
- PAR ID:
- 10644581
- Publisher / Repository:
- Electronic Journal of Combinatorics
- Date Published:
- Journal Name:
- The Electronic Journal of Combinatorics
- Volume:
- 32
- Issue:
- 3
- ISSN:
- 1077-8926
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
ABSTRACT A subgraph of a graph with maximum degree is ‐overfullif . Clearly, if contains a ‐overfull subgraph, then its chromatic index is . However, the converse is not true, as demonstrated by the Petersen graph. Nevertheless, three families of graphs are conjectured to satisfy the converse statement: (1) graphs with (the Overfull Conjecture of Chetwynd and Hilton), (2) planar graphs (Seymour's Exact Conjecture), and (3) graphs whose subgraph induced on the set of maximum degree vertices is the union of vertex‐disjoint cycles (the Core Conjecture of Hilton and Zhao). Over the past decades, these conjectures have been central to the study of edge coloring in simple graphs. Progress had been slow until recently, when the Core Conjecture was confirmed by the authors in 2024. This breakthrough was achieved by extending Vizing's classical fan technique to two larger families of trees: the pseudo‐multifan and the lollipop. This paper investigates the properties of these two structures, forming part of the theoretical foundation used to prove the Core Conjecture. We anticipate that these developments will provide insights into verifying the Overfull Conjecture for graphs where the subgraph induced by maximum‐degree vertices has relatively small maximum degree.more » « less
-
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
-
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
-
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
