Seymour's Second Neighborhood Conjecture

Related problems

SSNC implies two other partial results: the Behzad–Chartrand–Wall Conjecture and the Caccetta–Häggkvist Conjecture.

Behzad–Chartrand–Wall Conjecture (1970)

First I need to introduce three new definitions. A d-regular oriented graph is an oriented graph in which each vertex has both in-degree d and out-degree d. The girth of a graph is the length (i.e. the number of edges) of a shortest cycle in the graph. A directed cage is defined as the smallest d-regular oriented graph of girth g.

The Behzad–Chartrand–Wall Conjecture states that the number of vertices n of a directed cage is given by n = (g - 1)d + 1. SSNC implies the case d = ⌈n/3⌉ of this conjecture.

Caccetta–Häggkvist Conjecture (1978)

This conjecture states that given an oriented graph Γ of order n, in which the out-degree of every vertex v in G is at least d, the girth of Γ is at most ⌈n/d⌉. SSNC implies the interesting case of d = n/3.

The Caccetta–Häggkvist Conjecture was proven for d = 2 by Caccetta and Häggkvist, for d = 3 by Hamidoune and for d = 4, 5 by Hoáng and Reed. Shen also proved it for d ≤ √ n/2 . More details about the Caccetta–Häggkvist Conjecture can be found here.


More information about both the Behzad–Chartrand–Wall Conjecture and the Caccetta–Häggkvist Conjecture can be read in a nice presentation by Adrian Bondy.