Reed, Bruce A.

Forcing a 2-regular minor ★★

Author(s): Reed; Wood

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

Keywords: minors

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

Weighted colouring of hexagonal graphs. ★★

Author(s): McDiarmid; Reed

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


Hoàng-Reed Conjecture ★★★

Author(s): Hoang; Reed

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


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.

\begin{conjecture} Let $D$ be a digraph. If $|A(D)| > (k-2) |V(D)|$, then $D$ contains every antidirected tree of order $k$. \end{conjecture}


Domination in cubic graphs ★★

Author(s): Reed

\begin{problem} Does every 3-connected cubic graph $G$ satisfy $\gamma(G) \le \lceil |G|/3 \rceil$ ? \end{problem}

Keywords: cubic graph; domination

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

Author(s): Kostochka; Reed

\begin{conjecture} A triangle-free graph with maximum degree $\Delta$ has chromatic number at most $\ceil{\frac{\Delta}{2}}+2$. % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{conjecture}

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

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 \Def[clique]{clique (graph theory)} subgraph, and $\chi(G)$ to be the chromatic number of $G$.

\begin{conjecture} $\chi(G) \le \ceil{\frac{1}{2}(\Delta(G)+1) + \frac{1}{2}\omega(G)}$ for every graph $G$. \end{conjecture}

Keywords: coloring

Syndicate content