Characterizing the $\vec{\mathcal{P}}$-forcing graphs and the Second Neighborhood Conjecture for oriented graphs missing them

Seymour's Second Neighborhood Conjecture (SNC) asserts that every oriented graph has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood; it remains open in general. For an oriented graph $D$, its missing graph $G$ is the graph formed by the pairs of vertices joined by no arc, and the dependency digraph $\Delta_D$ has the missing edges of $D$ as vertices, with an arc from one missing edge to another when the first 'loses to' the second. Al-Mniny and Ghazal (Australas. J. Combin. 81 (2021), 58-88) introduced the class $\mathcal{F}(\vec{\mathcal{P}})$ of graphs $G$ such that $\Delta_D$ is a vertex-disjoint union of directed paths for every oriented graph $D$ missing $G$, proved SNC for oriented graphs missing any $\{C_4,\overline{C}_4,S_3,\text{chair},\overline{\text{chair}}\}$-free graph, and posed two open problems: (1) characterize $\mathcal{F}(\vec{\mathcal{P}})$ beyond the partial characterization they obtained, and (2) decide whether every oriented graph missing a graph in $\mathcal{F}(\vec{\mathcal{P}})$ — in the published formulation, in $\mathcal{F}(\vec{\mathcal{P}}\cup\vec{\mathcal{C}}_5)$, which also permits one directed 5-cycle component in $\Delta_D$ — satisfies the SNC. Both problems remain open.

Background

An oriented graph is a directed graph without loops and without digons, so each pair of distinct vertices is joined by at most one arc. For a vertex $v$, the first out-neighborhood $N^+(v)$ is its set of out-neighbors, and the second out-neighborhood $N^{++}(v)$ is the set of vertices reachable from $v$ by a directed path of exactly two arcs but not lying in $N^+(v)$. Seymour's Second Neighborhood Conjecture (SNC), posed around 1990, asserts that every oriented graph has a vertex $v$ with $|N^+(v)|\le|N^{++}(v)|$; such a vertex has the second neighborhood property (SNP). The conjecture is open in general. It was proved for tournaments (oriented complete graphs) by Fisher, following the tournament version conjectured by Dean and Latka, and Havet and Thomassé gave an influential shorter proof via median orders — a linear order of the vertices maximizing the number of forward arcs, whose last vertex (the feed vertex) has the SNP in tournaments. Kaneko and Locke verified the SNC for all oriented graphs of minimum out-degree at most 6.

A recurring route to dense, non-complete instances studies oriented graphs with few missing edges. A pair $xy$ of vertices of an oriented graph $D$ is a missing edge if neither $(x,y)$ nor $(y,x)$ is an arc; vertices incident to no missing edge are whole, and the missing graph of $D$ is the graph $G$ whose vertex set is the non-whole vertices and whose edge set is the missing edges — one says $D$ is missing $G$. Fidler and Yuster proved the SNC when the missing edges form a matching, a star, or a clique, introducing the dependency digraph: its vertices are the missing edges of $D$, and there is an arc from the missing edge $x_1y_1$ to the missing edge $x_2y_2$ when $x_1\to x_2$ with $y_2\notin N^+(x_1)\cup N^{++}(x_1)$, and $y_1\to y_2$ with $x_2\notin N^+(y_1)\cup N^{++}(y_1)$ (one then says $x_1y_1$ loses to $x_2y_2$). A missing edge is good when one of its two orientations is 'convenient' in the sense that every vertex dominating one endpoint sees the other endpoint within directed distance two; Ghazal proved that a missing edge is good exactly when its in-degree in the dependency digraph is zero, and used this to prove the SNC for every oriented graph missing a threshold graph — a graph built by iteratively adding isolated or universal vertices, equivalently a $\{C_4,\overline{C}_4,P_4\}$-free graph, where $C_n$ is the chordless $n$-cycle, $\overline{C}_4$ its complement, and $P_n$ the chordless $n$-vertex path. For threshold graphs the dependency digraph is always empty.

Al-Mniny and Ghazal generalized this framework. For a family $\mathcal{H}$ of digraphs, a graph $G$ is $\mathcal{H}$-forcing, written $G\in\mathcal{F}(\mathcal{H})$, when for every oriented graph $D$ missing $G$ the dependency digraph $\Delta_D$ belongs to $\mathcal{H}$. They let $\vec{\mathcal{P}}$ be the family of digraphs that are vertex-disjoint unions of directed paths. Using the structure theory of generalized combs — the graphs with no induced $C_4$, $\overline{C}_4$, $C_5$, $S_3$, chair, or co-chair, where the chair is the 5-vertex tree with edge set $\{xy,yz,zt,zv\}$, the co-chair is its complement, and $S_3$ is a fixed 6-vertex graph defined by Ghazal — they proved: (i) among $\{C_4,C_5,S_3\}$-free graphs, the $\vec{\mathcal{P}}$-forcing graphs are exactly the generalized combs; (ii) $\mathcal{F}(\vec{\mathcal{P}})$ is closed under taking induced subgraphs; (iii) threshold graphs are $\vec{\mathcal{P}}$-forcing; and (iv) the 5-cycle $C_5$ and all $\{C_4,\overline{C}_4,S_3,\text{chair},\overline{\text{chair}}\}$-free graphs are $\vec{\mathcal{P}}\cup\vec{\mathcal{C}}_5$-forcing, where $\vec{\mathcal{P}}\cup\vec{\mathcal{C}}_5$ is the family of digraphs that are vertex-disjoint unions of directed paths together with at most one directed 5-cycle (the source's shorthand for this family is $\vec{\mathcal{C}}_5=\{\vec{C}_5\}$ with $\vec{C}_5$ the directed 5-cycle). Their main theorem proves the SNC for every oriented graph missing a $\{C_4,\overline{C}_4,S_3,\text{chair},\overline{\text{chair}}\}$-free graph, by the completion approach: orient the missing edges according to their behavior in the dependency digraph so as to obtain a tournament, take a median order, and show its feed vertex retains the SNP when the added arcs are removed — the long case analysis being driven exactly by $\Delta_D$ being a disjoint union of directed paths plus possibly one directed 5-cycle. As corollaries, the SNC holds for oriented graphs missing a generalized comb, a comb, a threshold graph, or $C_5$.

The paper ends by posing the following two open problems: characterize $\mathcal{F}(\vec{\mathcal{P}})$ in full generality, and decide whether membership in the forcing class alone — without any additional forbidden-induced-subgraph hypothesis — already guarantees the SNC. The two halves are tightly linked: the first supplies the structural language in which the second, conjectural half is posed, and together they delineate the exact scope of the dependency-digraph/median-order method inside the broader missing-graph program for the SNC.

Problem Statement

Throughout, an oriented graph is a directed graph without loops and without digons, so each pair of distinct vertices is joined by at most one arc. For a vertex $v$ of an oriented graph, $N^+(v)$ denotes the set of out-neighbors of $v$, and $N^{++}(v)$ denotes the set of vertices reachable from $v$ by a directed path of exactly two arcs and not belonging to $N^+(v)$. A pair of vertices of an oriented graph $D$ is a missing edge when neither of the two arcs between them is present; the missing graph of $D$ is the graph whose vertex set is the set of vertices of $D$ incident with at least one missing edge and whose edge set is the set of missing edges, and one says that $D$ is missing $G$ when $G$ is the missing graph of $D$. Write $C_n$ for the chordless cycle on $n$ vertices and $\overline{C}_4$ for the complement of $C_4$.

Let $\vec{\mathcal{P}}$ be the family of digraphs each of which is a vertex-disjoint union of directed paths, and let $\vec{\mathcal{P}}\cup\vec{\mathcal{C}}_5$ be the family of digraphs that are vertex-disjoint unions of directed paths together with at most one directed cycle of length 5 (the source's shorthand is $\vec{\mathcal{C}}_5=\{\vec{C}_5\}$ with $\vec{C}_5$ the directed 5-cycle). For a family $\mathcal{H}$ of digraphs, let $\mathcal{F}(\mathcal{H})$ denote the class of graphs $G$ such that for every oriented graph $D$ missing $G$, the dependency digraph $\Delta_D$ belongs to $\mathcal{H}$; the vertices of $\Delta_D$ are the missing edges of $D$, and there is an arc from the missing edge $x_1y_1$ to the missing edge $x_2y_2$ when $x_1\to x_2$ with $y_2\notin N^+(x_1)\cup N^{++}(x_1)$, and $y_1\to y_2$ with $x_2\notin N^+(y_1)\cup N^{++}(y_1)$ (one then says that $x_1y_1$ loses to $x_2y_2$). The source paper poses two linked problems:

(Problem A, their Problem 1). Characterize $\mathcal{F}(\vec{\mathcal{P}})$: give a structural description of all graphs $G$ such that the dependency digraph of every oriented graph missing $G$ is a disjoint union of directed paths. The known partial answer is that, restricted to $\{C_4,C_5,S_3\}$-free graphs (where $S_3$ is the specific 6-vertex graph defined by Ghazal, 2018), $\mathcal{F}(\vec{\mathcal{P}})$ consists exactly of the generalized combs, that is, the graphs with no induced $C_4$, $\overline{C}_4$, $C_5$, $S_3$, chair, or co-chair, where the chair is the 5-vertex tree with edge set $\{xy,yz,zt,zv\}$ and the co-chair is its complement; the characterization is required without this restriction.

(Problem B, their Problem 2). Does every oriented graph missing a graph $G\in\mathcal{F}(\vec{\mathcal{P}}\cup\vec{\mathcal{C}}_5)$ satisfy Seymour's Second Neighborhood Conjecture, i.e., contain a vertex $v$ with $|N^+(v)|\le|N^{++}(v)|$? It is known that the answer is yes when $G$ is additionally $\{C_4,\overline{C}_4,S_3,\text{chair},\overline{\text{chair}}\}$-free (this is the main theorem of the source); the question is whether the forcing condition alone suffices.

The two deliverables share one scientific objective — determining the exact scope of the dependency-digraph/median-order method in the missing-graph program for the SNC — with Problem A supplying the structural description of the forcing class and Problem B deciding whether that structural condition already guarantees the conjecture. The two problems are logically independent: a characterization of $\mathcal{F}(\vec{\mathcal{P}})$ does not by itself decide the SNC question, and a resolution of Problem B does not by itself characterize $\mathcal{F}(\vec{\mathcal{P}})$, so neither answer substitutes for the other and each requires its own resolution.

References

1. Darine Al-Mniny and Salman Ghazal, The second neighborhood conjecture for oriented graphs missing a $\{C_4,\overline{C}_4,S_3,\text{chair and }\overline{\text{chair}}\}$-free graph, Australasian Journal of Combinatorics 81(1) (2021), 58-88, zbMATH 7471094, https://zbmath.org/7471094 (arXiv:2010.10790, whose title variant reads 'chair and co-chair', https://arxiv.org/abs/2010.10790); published version: https://ajc.maths.uq.edu.au/pdf/81/ajc_v81_p058.pdf
2. Moussa Daamouch, Salman Ghazal, and Darine Al-Mniny, About the second neighborhood conjecture for tournaments missing two stars or disjoint paths, Contributions to Discrete Mathematics 20(2) (2025), 363-383, DOI 10.55016/ojs/cdm.v20i2.77499, https://doi.org/10.55016/ojs/cdm.v20i2.77499 (arXiv:2406.03635)
3. Suresh Dara, Mathew C. Francis, Dalu Jacob, and N. Narayanan, Extending some results on the second neighborhood conjecture, Discrete Applied Mathematics 311 (2022), 1-17, DOI 10.1016/j.dam.2021.12.034, https://doi.org/10.1016/j.dam.2021.12.034 (arXiv:1808.02247)
4. Dror Fidler and Raphael Yuster, Remarks on the second neighborhood problem, Journal of Graph Theory 55(3) (2007), 208-220, DOI 10.1002/jgt.20229, https://doi.org/10.1002/jgt.20229
5. David C. Fisher, Squaring a tournament: a proof of Dean's conjecture, Journal of Graph Theory 23(1) (1996), 43-48, 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
6. Frédéric Havet and Stéphan Thomassé, Median orders of tournaments: a tool for the second neighborhood problem and Sumner's conjecture, Journal of Graph Theory 35(4) (2000), 244-256, 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
7. Yoshihiro Kaneko and Stephen C. Locke, The minimum degree approach for Paul Seymour's distance 2 conjecture, Congressus Numerantium 148 (2001), 201-206, zbMATH 1743979, https://zbmath.org/?q=an%3A1743979
8. Salman Ghazal, Seymour's second neighborhood conjecture for tournaments missing a generalized star, Journal of Graph Theory 71(1) (2012), 89-94, DOI 10.1002/jgt.20634, https://doi.org/10.1002/jgt.20634 (arXiv:1106.0085)
9. Salman Ghazal, The structure of graphs with forbidden induced $C_4$, $\overline{C}_4$, $C_5$, $S_3$, chair and co-chair, Electronic Journal of Graph Theory and Applications 6(2) (2018), 219-227, DOI 10.5614/ejgta.2018.6.2.2, https://doi.org/10.5614/ejgta.2018.6.2.2
10. Haozhe Wang and Mei Lu, Seymour's second neighborhood conjecture for some oriented graphs, Graphs and Combinatorics 42(2) (2026), Paper No. 19, DOI 10.1007/s00373-026-03014-y, https://doi.org/10.1007/s00373-026-03014-y
11. Jake Brukhman, A dense-case theorem for Seymour's second neighborhood conjecture, arXiv:2608.11530 (2026), https://arxiv.org/abs/2608.11530
12. Arpan Sadhukhan, R. B. Sandeep, and 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
13. Charles N. Glover, A minimum counterexample proof of the Seymour second neighborhood conjecture via the graph level order, arXiv:2501.00614 (2025), https://arxiv.org/abs/2501.00614