Seymour, Paul D.

Fractional Hadwiger ★★

Conjecture For every graph $G$ ,
(a) $\chi_f(G)\leq\text{had}(G)$
(b) $\chi(G)\leq\text{had}_f(G)$
(c) $\chi_f(G)\leq\text{had}_f(G)$ .

Keywords: fractional coloring, minors

Posted by David Wood
updated March 16th, 2014

add new comment

Graph Theory » Coloring » Edge coloring

Seymour's r-graph conjecture ★★★

Author(s): Seymour

An $r$ -graph is an $r$ -regular graph $G$ with the property that $|\delta(X)| \ge r$ for every $X \subseteq V(G)$ with odd size.

Conjecture $\chi'(G) \le r+1$ for every $r$ -graph $G$ .

Keywords: edge-coloring; r-graph

Posted by mdevos
updated October 3rd, 2008

add new comment

Graph Theory » Directed Graphs

Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph $G$ , we let $\gamma(G)$ be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and $\beta(G)$ be the size of the smallest feedback edge set.

Conjecture If $G$ is a simple digraph without directed cycles of length $\le 3$ , then $\beta(G) \le \frac{1}{2} \gamma(G)$ .

Keywords: acyclic; digraph; feedback edge set; triangle free

Posted by mdevos
updated July 8th, 2008

add new comment

Graph Theory » Basic G.T. » Minors

Seagull problem ★★★

Author(s): Seymour

Conjecture Every $n$ vertex graph with no independent set of size $3$ has a complete graph on $\ge \frac{n}{2}$ vertices as a minor.

Keywords: coloring; complete graph; minor

Posted by mdevos
updated January 6th, 2008

add new comment

Graph Theory » Directed Graphs

Seymour's Second Neighbourhood Conjecture ★★★

Author(s): Seymour

Conjecture Any oriented graph has a vertex whose outdegree is at most its second outdegree.

Keywords: Caccetta-Häggkvist; neighbourhood; second; Seymour

Posted by nkorppi
updated March 18th, 2011

5 comments

Combinatorics » Matroid Theory

Bases of many weights ★★★

Author(s): Schrijver; Seymour

Let $G$ be an (additive) abelian group, and for every $S \subseteq G$ let ${\mathit stab}(S) = \{ g \in G : g + S = S \}$ .

Conjecture Let $M$ be a matroid on $E$ , let $w : E \rightarrow G$ be a map, put $S = \{ \sum_{b \in B} w(b) : B \mbox{ is a base} \}$ and $H = {\mathit stab}(S)$ . Then $|S| \ge |H| \left( 1 - rk(M) + \sum_{Q \in G/H} rk(w^{-1}(Q)) \right).$

Keywords: matroid; sumset; zero sum

Posted by mdevos
updated June 10th, 2007

add new comment

Graph Theory » Coloring » Vertex coloring

Alon-Saks-Seymour Conjecture ★★★

Author(s): Alon; Saks; Seymour

Conjecture If $G$ is a simple graph which can be written as an union of $m$ edge-disjoint complete bipartite graphs, then $\chi(G) \le m+1$ .

Keywords: coloring; complete bipartite graph; eigenvalues; interlacing

Posted by mdevos
updated February 26th, 2010

1 comment

Graph Theory » Infinite Graphs

Seymour's self-minor conjecture ★★★

Author(s): Seymour

Conjecture Every infinite graph is a proper minor of itself.

Keywords: infinite graph; minor

Posted by mdevos
updated April 15th, 2010

2 comments

Graph Theory » Basic G.T. » Cycles

Faithful cycle covers ★★★

Author(s): Seymour

Conjecture If $G = (V,E)$ is a graph, $p : E \rightarrow {\mathbb Z}$ is admissable, and $p(e)$ is even for every $e \in E(G)$ , then $(G,p)$ has a faithful cover.