Seymour's and Sullivan's second-neighbourhood conjectures for oriented split graphs and multipartite tournaments

Seymour's second-neighbourhood conjecture (1995) asserts that every oriented graph has a vertex whose second out-neighbourhood is at least as large as its first out-neighbourhood; Sullivan's conjecture (2006) asserts that every oriented graph has a vertex whose second out-neighbourhood is at least as large as its in-neighbourhood. Both conjectures are open in general, and Ai, Gerke, Gutin, Wang, Yeo, and Zhou (2023) explicitly highlighted two natural intermediate classes that resist current methods: oriented split graphs (whose vertex set partitions into an independent set $X$ and a set $Y$ inducing a tournament) and multipartite tournaments (orientations of complete multipartite graphs). This problem asks whether either conjecture, or both, can be proved for all oriented split graphs and for all multipartite tournaments. The only known partial results cover complete oriented split graphs, split graphs whose tournament part is regular or almost regular, and small bounded source-free cases; the general cases, posed by the source paper in 2023 and restated as open in its July 2026 revision, remain unsolved.

Background

An oriented graph is a directed graph in which between every pair of distinct vertices there is at most one arc; equivalently, it is an orientation of a simple undirected graph. For a vertex $u$ of an oriented graph $D$, the first out-neighbourhood $N^{+}(u)$ is the set of heads of arcs leaving $u$, the in-neighbourhood $N^{-}(u)$ is the set of tails of arcs entering $u$, and the second out-neighbourhood $N^{++}(u)$ is the set of vertices reachable from $u$ by a directed path of length exactly two but not lying in $N^{+}(u)$; $d^{+}(u)$, $d^{-}(u)$, $d^{++}(u)$ denote the corresponding cardinalities.

In 1978 Caccetta and Häggkvist conjectured that every digraph on $n$ vertices with minimum out-degree at least $n/r$ contains a directed cycle of length at most $r$; the case $r=3$ is one of the most famous open problems in graph theory. In this context, Seymour (1995; the conjecture appears in print via Dean and Latka, 1995) proposed a weaker-looking statement that would imply the special case of Caccetta–Häggkvist where both minimum in- and out-degrees are at least $n/3$: every oriented graph has a vertex $u$ (a Seymour vertex) with $d^{++}(u) \ge d^{+}(u)$. Sullivan (2006) proposed the companion statement that every oriented graph has a vertex $u$ (a Sullivan vertex) with $d^{++}(u) \ge d^{-}(u)$, which implies the same special case of Caccetta–Häggkvist; note that a source vertex (one with empty in-neighbourhood) is trivially a Sullivan vertex, so only source-free digraphs need attention for Sullivan's conjecture. Both conjectures are easily seen to fail for general digraphs with arcs in both directions between two vertices (a complete biorientation of a complete graph has no Seymour vertex), which is why they are posed for oriented graphs.

Confirmed cases of Seymour's conjecture include tournaments (orientations of complete graphs; Fisher 1996, with another proof by Havet and Thomassé 2000 via median orders, which are orderings of the vertices of a tournament that minimise the number of backward arcs), tournaments in which the edges missing from completeness form a star, two stars, or a family of disjoint paths (Ghazal 2012; Daamouch, Ghazal and Al-Mniny 2025), oriented graphs whose missing edges form further restricted configurations, such as a clique (equivalently, complete oriented split graphs), or a matching together with a star (Fidler and Yuster 2007; Dara, Francis, Jacob and Narayanan 2022; Wang and Lu 2026), and oriented graphs of minimum out-degree at most 6 (Kaneko and Locke 2001) and, by a 2026 partly computer-assisted preprint of Sadhukhan, Sandeep and Sen, minimum out-degree exactly 7. Huang and Peng (2024) proved the best constant-factor relaxation: every oriented graph has a vertex with $d^{++}(u) \ge 0.715538\,d^{+}(u)$. Sullivan's conjecture was confirmed for local tournaments (oriented graphs in which the in-neighbourhood and the out-neighbourhood of every vertex each induce a tournament), bipartite tournaments, and quasi-transitive oriented graphs (oriented graphs in which any two vertices connected by a directed path of length two are adjacent) (Li and Sheng 2018, 2019; Li and Liang 2020), for oriented graphs of minimum degree at least $n-3$ (El Zein 2025), and, by the source paper of this problem, for all tournaments, all orientations of triangle-free graphs, all orientations of planar graphs, and asymptotically almost every oriented graph.

A split graph is a graph whose vertex set partitions into a clique and an independent set; an oriented split graph is an orientation of such a graph, and will be written $D=(X,Y,A)$ with $X$ an independent set and $Y$ inducing a tournament. A complete oriented split graph is one in which every vertex of $X$ is adjacent to every vertex of $Y$. A multipartite tournament is an orientation of a complete multipartite graph, i.e. all edges between different partite sets are present and oriented while partite sets are independent. Tournaments are the special case where every partite set is a singleton, and a complete oriented split graph is a multipartite tournament in which all but one partite set are singletons; a general oriented split graph, however, need not be a multipartite tournament. Ai, Gerke, Gutin, Wang, Yeo and Zhou (2023) proved Sullivan's conjecture for all complete oriented split graphs, and both conjectures for oriented split graphs whose part $Y$ induces a regular tournament (every vertex has equal in- and out-degree within $Y$) or an almost regular tournament (these in- and out-degrees differ by at most one). However, they were unable to verify either conjecture for arbitrary oriented split graphs, and in their discussion they singled out the class of multipartite tournaments as an explicit open target; their July 2026 revision of the paper restates both problems as open. Zhao (2026) subsequently proved Sullivan's conjecture for source-free oriented split graphs with $|X|=2$ or $|Y|\le 5$, and for source-free complete oriented split graphs with $|X|\le 4$ — bounded-size partial progress that confirms the difficulty of the unbounded general case.

Problem Statement

Prove or disprove each of the following four statements, which the source paper of Ai, Gerke, Gutin, Wang, Yeo and Zhou explicitly leaves open.

(1) Seymour's second-neighbourhood conjecture on split graphs: every oriented split graph $D=(X,Y,A)$ (an orientation of a graph whose vertex set partitions into an independent set $X$ and a set $Y$ inducing a tournament) contains a vertex $u$ with $d^{++}(u)\ge d^{+}(u)$.

(2) Sullivan's conjecture on split graphs: every oriented split graph $D=(X,Y,A)$ contains a vertex $u$ with $d^{++}(u)\ge d^{-}(u)$.

(3) Seymour's second-neighbourhood conjecture on multipartite tournaments: every multipartite tournament (orientation of a complete multipartite graph) contains a vertex $u$ with $d^{++}(u)\ge d^{+}(u)$.

(4) Sullivan's conjecture on multipartite tournaments: every multipartite tournament contains a vertex $u$ with $d^{++}(u)\ge d^{-}(u)$.

Every complete oriented split graph is a multipartite tournament, but a general oriented split graph need not be a multipartite tournament and a general multipartite tournament need not be an oriented split graph; the two classes are therefore incomparable, and the four statements are independent targets. A refutation of any statement takes the form of a finite counterexample: an explicitly given oriented split graph or multipartite tournament in which every vertex $u$ satisfies $d^{++}(u)<d^{+}(u)$ (refuting (1) or (3)) or $d^{++}(u)<d^{-}(u)$ (refuting (2) or (4)). The following special cases are already resolved and form no part of the open target: Seymour's conjecture for complete oriented split graphs and for oriented split graphs with $|X|=1$ (Fidler and Yuster 2007); Sullivan's conjecture for complete oriented split graphs (Ai et al. 2023); both conjectures for oriented split graphs whose part $Y$ induces a regular or an almost regular tournament (Ai et al. 2023); and Sullivan's conjecture for source-free oriented split graphs with $|X|=2$ or $|Y|\le 5$, and for source-free complete oriented split graphs with $|X|\le 4$ (Zhao 2026).

References

1. Jiangdong Ai, Stefanie Gerke, Gregory Gutin, Shujing Wang, Anders Yeo, Yacong Zhou, On Seymour's and Sullivan's second neighbourhood conjectures, Journal of Graph Theory 105(3):413–426 (2023), DOI 10.1002/jgt.23050, arXiv:2306.03493, https://doi.org/10.1002/jgt.23050
2. Blair Dowling Sullivan, A summary of problems and results related to the Caccetta-Haggkvist conjecture, arXiv:math/0605646 (2006), https://arxiv.org/abs/math/0605646
3. David C. Fisher, Squaring a tournament: A proof of Dean's conjecture, Journal of Graph Theory 23(1):43–48 (1996), DOI 10.1002/(SICI)1097-0118(199609)23:1<43::AID-JGT4>3.0.CO;2-K, https://doi.org/10.1002/(SICI)1097-0118(199609)23:1%3C43::AID-JGT4%3E3.0.CO;2-K
4. Salman Ghazal, Seymour's second neighborhood conjecture for tournaments missing a generalized star, Journal of Graph Theory 71(1):89–94 (2012), DOI 10.1002/jgt.20634, https://doi.org/10.1002/jgt.20634
5. Frédéric Havet, Stéphan Thomassé, Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture, Journal of Graph Theory 35(4):244–256 (2000), DOI 10.1002/1097-0118(200012)35:4<244::AID-JGT2>3.0.CO;2-H, https://doi.org/10.1002/1097-0118(200012)35:4%3C244::AID-JGT2%3E3.0.CO;2-H
6. Suresh Dara, Mathew C. Francis, Dalu Jacob, N. Narayanan, Extending some results on the second neighborhood conjecture, Discrete Applied Mathematics 311:1–17 (2022), DOI 10.1016/j.dam.2021.12.034, https://doi.org/10.1016/j.dam.2021.12.034
7. Haozhe Wang, Mei Lu, Seymour's second neighborhood conjecture for some oriented graphs, Graphs and Combinatorics 42(2) (2026), DOI 10.1007/s00373-026-03014-Y, https://doi.org/10.1007/s00373-026-03014-Y
8. Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen, A proof of Seymour's second neighborhood conjecture for oriented graphs with minimum out-degree equal to 7, arXiv:2606.30588 (2026), https://arxiv.org/abs/2606.30588
9. Hao Huang, Fei Peng, An improved bound on Seymour's second neighborhood conjecture, arXiv:2412.20234 (2024), https://arxiv.org/abs/2412.20234
10. Ayman El Zein, A note on Sullivan's second neighborhood conjecture, Graphs and Combinatorics 41(2) (2025), DOI 10.1007/s00373-025-02908-7, https://doi.org/10.1007/s00373-025-02908-7
11. Ruijuan Li, Bin Sheng, The second neighbourhood for bipartite tournaments, Discussiones Mathematicae Graph Theory 39:555–565 (2019), DOI 10.7151/dmgt.2018, https://doi.org/10.7151/dmgt.2018
12. Ruijuan Li, Juanjuan Liang, The second out-neighborhood for local tournaments, Open Mathematics 18:270–283 (2020), DOI 10.1515/math-2020-0026, https://doi.org/10.1515/math-2020-0026
13. Ruijuan Li, Bin Sheng, The second neighbourhood for quasi-transitive oriented graphs, Acta Mathematica Sinica, English Series 34:1391–1402 (2018), DOI 10.1007/s10114-018-7287-3, https://doi.org/10.1007/s10114-018-7287-3
14. Ruibo Zhao, A note on Sullivan's conjecture for oriented split graphs, Applied Mathematics and Computation 524:130033 (2026), DOI 10.1016/j.amc.2026.130033, https://doi.org/10.1016/j.amc.2026.130033
15. Alberto Espuny Díaz, António Girão, Bertille Granet, Gal Kronenberg, Seymour's second neighbourhood conjecture: random graphs and reductions, arXiv:2403.02842 (2024), https://arxiv.org/abs/2403.02842
16. Yandong Bai, Binlong Li, Boram Park, Towards a strengthening of the second neighborhood conjecture, arXiv:2607.18047 (2026), https://arxiv.org/abs/2607.18047
17. Jake Brukhman, A dense-case theorem for Seymour's second neighborhood conjecture, arXiv:2608.11530 (2026), https://arxiv.org/abs/2608.11530
18. Moussa Daamouch, Salman Ghazal, Darine Al-Mniny, About the second neighborhood conjecture for tournaments missing two stars or disjoint paths, Contributions to Discrete Mathematics 20(2):363–383 (2025), DOI 10.55016/ojs/cdm.v20i2.77499, https://doi.org/10.55016/ojs/cdm.v20i2.77499
19. Charles N. Glover, A Minimum Counterexample Proof of the Seymour Second Neighborhood Conjecture via the Graph Level Order, arXiv:2501.00614 (2024, revised through 2026), https://arxiv.org/abs/2501.00614
20. David Fidler, Raphael Yuster, Remarks on the second neighborhood problem, Journal of Graph Theory 55(3):208–220 (2007), DOI 10.1002/jgt.20229, https://doi.org/10.1002/jgt.20229