A feedback-set bound for second neighborhoods
Statement
Conjecture 3.
- (Seymour) Any simple digraph with no loops or digons has a vertex v whose second neighborhood is at least as big as its first neighborhood, i.e. |N +2 (v)| ≥ | N +(v)|.
The following is known for Seymour's second neighborhood conjecture:
• When G is a tournament, this is Dean's conjecture, and was proved by Fisher [13] using probabilistic methods. There is also a combinatorial proof by Havet and Thomass´ e [18].
• It was proved for digraphs with minimum outdegree ≤ 6 by Kaneko and Locke [20].
• There is a vertex v where |N +2 (v)| ≥ γ|N +(v)| and γ = 0.657298... is the unique real root of 2 x3 + x2 − 1 = 0. (Note the conjecture is that γ = 1) by Chen, Shen, and Yuster [7]. They also claim a slight improvement to γ = 0.67815 (proof unpublished).
• Godbole, Cole, and Wright [14] showed that the conjecture holds for almost all digraphs.
4 r-Regular Digraphs
A digraph G is r-regular if every vertex v has δ+
G
(v) = δ−
G
(v) = r.
Record
- Source
- Added
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.