Seymour, Paul D.


Fractional Hadwiger ★★

Author(s): Harvey; Reed; Seymour; Wood

\begin{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)$. \end{conjecture}

Keywords: fractional coloring, minors

Seymour's r-graph conjecture ★★★

Author(s): Seymour

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

\begin{conjecture} $\chi'(G) \le r+1$ for every $r$-graph $G$. \end{conjecture}

Keywords: edge-coloring; r-graph

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 \Def[feedback edge set]{feedback arc set}.

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

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

Seagull problem ★★★

Author(s): Seymour

\begin{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. \end{conjecture}

Keywords: coloring; complete graph; minor

Seymour's Second Neighbourhood Conjecture ★★★

Author(s): Seymour

\begin{conjecture} Any oriented graph has a vertex whose outdegree is at most its second outdegree. \end{conjecture}

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

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 \}$.

\begin{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).$$ \end{conjecture}

Keywords: matroid; sumset; zero sum

Alon-Saks-Seymour Conjecture ★★★

Author(s): Alon; Saks; Seymour

\begin{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$. \end{conjecture}

Keywords: coloring; complete bipartite graph; eigenvalues; interlacing

Seymour's self-minor conjecture ★★★

Author(s): Seymour

\begin{conjecture} Every infinite graph is a proper \Def[minor]{minor (graph theory)} of itself. \end{conjecture}

Keywords: infinite graph; minor

Faithful cycle covers ★★★

Author(s): Seymour

\begin{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. \end{conjecture}

Keywords: cover; cycle

Cycle double cover conjecture ★★★★

Author(s): Seymour; Szekeres

\begin{conjecture} For every graph with no \Def[bridge]{bridge (graph theory)}, there is a list of cycles so that every edge is contained in exactly two. \end{conjecture}

Keywords: cover; cycle

Syndicate content