ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Conjecture 3.

  1. (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

Added
Links

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.