Reed, Bruce A.

Forcing a 2-regular minor ★★

Author(s): Reed; Wood

Conjecture Every graph with average degree at least $\frac{4}{3}t-2$ contains every 2-regular graph on $t$ vertices as a minor.

Keywords: minors

Posted by David Wood
updated March 16th, 2014

add new comment

Graph Theory

Fractional Hadwiger ★★

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

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 » Vertex coloring

Weighted colouring of hexagonal graphs. ★★

Author(s): McDiarmid; Reed

Conjecture There is an absolute constant $c$ such that for every hexagonal graph $G$ and vertex weighting $p:V(G)\rightarrow \mathbb{N}$ , $\chi(G,p) \leq \frac{9}{8}\omega(G,p) + c$

Keywords:

Posted by fhavet
updated March 13th, 2013

add new comment

Graph Theory » Directed Graphs

Conjecture Every digraph in which each vertex has outdegree at least $k$ contains $k$ directed cycles $C_1, \ldots, C_k$ such that $C_j$ meets $\cup_{i=1}^{j-1}C_i$ in at most one vertex, $2 \leq j \leq k$ .

Keywords:

Posted by fhavet
updated March 11th, 2013

add new comment

Graph Theory » Directed Graphs

Antidirected trees in digraphs ★★

Author(s): Addario-Berry; Havet; Linhares Sales; Reed; Thomassé

An antidirected tree is an orientation of a tree in which every vertex has either indegree 0 or outdergree 0.

Conjecture Let $D$ be a digraph. If $|A(D)| > (k-2) |V(D)|$ , then $D$ contains every antidirected tree of order $k$ .

Keywords:

Posted by fhavet
updated February 26th, 2013

add new comment

Graph Theory » Basic G.T.

Domination in cubic graphs ★★

Author(s): Reed

Problem Does every 3-connected cubic graph $G$ satisfy $\gamma(G) \le \lceil |G|/3 \rceil$ ?

Keywords: cubic graph; domination

Posted by mdevos
updated August 19th, 2009

add new comment

Graph Theory » Coloring » Vertex coloring

Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

Conjecture A triangle-free graph with maximum degree $\Delta$ has chromatic number at most $\ceil{\frac{\Delta}{2}}+2$ .

Keywords: chromatic number; girth; maximum degree; triangle free

Posted by Andrew King
updated May 16th, 2020

1 comment

Graph Theory » Coloring » Vertex coloring

Reed's omega, delta, and chi conjecture ★★★

Author(s): Reed

For a graph $G$ , we define $\Delta(G)$ to be the maximum degree, $\omega(G)$ to be the size of the largest clique subgraph, and $\chi(G)$ to be the chromatic number of $G$ .