12 problems

For a graph $G$, write $\chi(G)$ for its chromatic number and $\operatorname{girth}(G)$ for its girth. Erdős's conjecture. Given any two natural numbers $g,r\geq 2$, there exists a…

Let $G=(V,E)$ be a simple graph, where $V$ is its vertex set. A graph is critically $s$-chromatic if it has chromatic number $s$ and deleting any vertex lowers its chromatic number…

Let $F$ be a graph with at least one edge. The cited theorem provides a constant $c(F)$ such that, for every natural number $r$, there is a graph $G$ with $\chi(G)>r$,…

For a graph $F$ with at least one edge, let $\chi(F)$, $\omega(F)$, and $\operatorname{girth}(F)$ denote its chromatic number, clique number, and girth. The cited theorem asserts t…

For a graph $G$, let $\chi(G)$ denote its chromatic number, and call $G$ $K_4$-free if it contains no complete subgraph on four vertices. Galvin–Rödl conjecture. It suffices to ass…

Let $F$ be a graph with chromatic number $r+1$ and a color-critical edge, meaning an edge whose removal decreases the chromatic number. Let $H$ be weakly $F$-Turán-good if, for all…

Let $G^*$ denote the graph characterized in the paper as the extremal $n$-vertex $k$-chromatic … -connected graph, then … The conjecture is known for $k=3$ and $=2$ when $n5$, whil…

Let $G^*$ denote the graph characterized in the paper as the extremal $n$-vertex $k$-chromatic … -connected graph, then … Theorem characterizes $G^*$ for large $n$, and this conjec…

Let $G$ be a connected $k$-chromatic graph. In a $k$-coloring, a certifying path is a path whose vertices meet the required distinct color classes, and call such a path forward or…

A connected graph is double-critical $k$-chromatic if it has chromatic number $k$ and, for every edge $uv$, deleting $u$ and $v$ lowers the chromatic number by $2$. Double-Critical…

Let $G$ be a graph that is critically $s$-chromatic, meaning that its chromatic number is $s$ and deleting any vertex lowers the chromatic number. For a subset $W$ of the vertices…

Chromatic tree-packing conjecture. If $G$ is a $k$-chromatic graph, then the set of trees $T_2,\dots,T_k$ has a packing into $G$.