Originators: Bruce Reed (presented by Andrew King - REGS 2011)
Definitions: The claw is the graph $K_{1,3}$; the bull is the self-complementary $5$-vertex graph consisting of a triangle plus two pendant edges. A graph is claw-free if it has no claw as an induced subgraph. A graph is bull-free if it has no bull as an induced subgraph.
Background: Reed's Conjecture on $\omega$, $\Delta$, and $\chi$ is a major open problem in the area of graph colouring.
Conjecture 1: (Reed [R]) For any graph $G$, $\chi(G) \leq \left\lceil \frac {\Delta(G)+1+\omega(G)}2 \right\rceil$.
Comments: Conjecture 1 is known to hold for several classes of graphs, including: Claw-free graphs (this includes line graphs and graphs with $\alpha \leq 2$), graphs having no induced odd cycles of length at least $5$, and graphs whose chromatic number is the ceiling of their fractional chromatic number.
It would be nice to prove the conjecture for bull-free graphs. Bull-free graphs are an attractive target for two reasons. First, there is a potentially useful structure theorem due to Chudnovsky [C]. Second, the family is closed under complementation, like the family of perfect graphs where the conjecture obviously holds. However, the conjecture is not known to hold even for the family of triangle-free graphs, which is contained in the family of bull-free graphs. When $\omega(G)=2$, the conjecture reduces to
Conjecture 2: If $G$ is a triangle-free graph, then $\chi(G) \le\frac{\Delta(G)} 2 +2$.
Comments: When $\Delta(G)$ is large, the conjecture holds easily, since Johansson [J] proved that $\chi(G) \leq 9\Delta(G)/\log\Delta(G)$ when $G$ is triangle-free. For $\Delta(G)\leq 4$, the inequality follows immediately from Brooks' Theorem. Also, Kostochka proved that $\chi(G)\leq \frac 23 \Delta(G)+ 2$ when $G$ is triangle-free (see [JT, section 4.6]) and that $\chi(G)\leq \frac {\Delta(G)}2+ 2$ when $G$ has girth at least $4(\Delta(G)+2)\log \Delta(G)$ [Ko]. So, let's just consider a first case:
Problem 3: Prove that any triangle-free graph with maximum degree at most 6 is 5-colorable.
Comments: The above result would be implied by the harder one below.
Problem 4: Prove that any triangle-free graph with maximum degree at most 5 is 4-colourable.
Comments: We can also study Reed's Conjecture by obtaining properties of smallest counterexamples. King [Ki] proved that every graph $G$ such that $\omega(G)\gt\frac23(\Delta(G)+1)$ contains a stable set that intersects every maximum clique. The method of proof can be extended to characterize what happens when $\omega(G) = \frac23(\Delta(G)+1)$. Edwards and King [EK] showed as a corollary that if $G$ is a graph satisfying $\omega(G)\ge\frac23(\Delta(G)+1)$ that has no stable set intersecting every maximum clique, then $G$ is the strong product of a complete graph with an odd cycle. We conclude that if $G$ is a smallest counterexample to Reed's Conjecture (restricted to any hereditary class of graphs), then $\omega(G)\leq\frac23(\Delta(G)+1)$.
A set $S\subseteq V(G)$ is $k$-chromatic if $\chi(G[S])=k$. We can restate the corollary above as follows: If $G$ is a graph such that $\omega(G)\gt\frac23(\Delta(G)+1)$, then there is a 1-chromatic set $S\subseteq V(G)$ such that $\omega(G-S)+\Delta(G-S)\le\omega(G)+\Delta(G)-2$. If we allow ourselves to remove more than one stable set from a supposed minimum counterexample, can we do a little better?
Problem 5: Do there exist constants $c,k,\Delta_0$ with $c\lt\frac 23$, $k\gt1$, and $\Delta_0\in\mathbb{N}$ such that every graph $G$ satisfying $\omega(G) \gt c(\Delta(G)+1)$ and $\Delta(G)\gt\Delta_0$ has a $k$-chromatic vertex subset $S$ such that $\omega(G-S)+\Delta(G-S)\le\omega(G)+\Delta(G)-2k$.
Comments: For the strong product of a complete graph with at least two vertices and an odd cycle, we can remove $5$ stable sets to reduce the clique number by at least 4 and the maximum size of a closed neighbourhood by at least 6.
References:
[C] M. Chudnovsky, The structure of bull-free graphs III: global structure.
(2008, manuscript.)
[J] A. Johansson, Asymptotic choice number for triangle-free graphs,
DIMACS Tech. Report 19-5 (1996).
[EK] K. Edwards and A.D. King, unpublished.
[Ki] A.D. King, Hitting all maximum cliques with a stable set using lopsided
independent transversals, J. Graph Theory 67 (2010), 300-305.
[Ko] A.V. Kostochka. Degree, girth, and chromatic number. In Combinatorics
(Proc. Fifth Hungarian Colloq., Keszthely, 1976), volume 18, pages 679-696.
North- Holland, 1978.
[R] B.A. Reed, $\omega$, $\Delta$, and $\chi$,
J. Graph Theory 27 (1998), 177-212.