56 problems

Let $r\ge 2$ and $k\ge 0$, and let $G$ be a connected graph of order $n\ge 2(2r+k+2)(r+k+2)$ with minimum degree $\delta(G)\ge r+k$. Let $F_n^{r,k}$ be the extremal graph appearing…

Let $G$ be a finite, undirected, loopless multigraph. Write $\Delta=\Delta(G)$ for its maximum degree, $\chi'(G)$ for its chromatic index, and $\overline{d}(G)$ for its average deg…

Let $G^*$ be an $n$-vertex connected class 1 $\Delta$-regular graph with $\Delta>\frac{n}{3}$. A vertex-splitting replaces a vertex by two adjacent vertices whose neighborhoods par…

Ore's conjecture. If $k\geq4$, then

A connected graph $G$ is double-critical if $\chi(G)=t$ and … for every edge $xy\in E(G)$. Double-Critical Graph Conjecture. For every integer $t\geq3$, the only double-critical…

Let $k\geq 3$ and let $G$ be a $k$-critical graph. Let $\mu(G)$ denote the matching number and $\mu_f(G)$ the fractional matching number. Fractional matching gap conjecture. If $G$…

Dirac's conjecture. For every integer $k\ge 4$, there exists a $k$-vertex-critical graph none of whose edges is critical. Equivalently, removing any edge from the graph does not al…

Let $G$ be a graph such that removing every edge reduces its chromatic number by two. Double-critical graph conjecture. Then $G$ is a complete graph. This is the $s=2$ case of the…

Gallai's conjecture. Every $k$-critical graph $G$ on $n$ vertices satisfies

Postle's conjecture. For every $k\geq4$, there exists $\varepsilon_k>0$ such that if $G$ is a $k$-critical $K_{k-2}$-free graph, then

Circular-colouring density conjecture. If $G$ has no $(p,q)$-colouring, then there exist positive rational numbers $\varepsilon_{p,q}$ and $c_{p,q}$, depending on $p$ and $q$, such…

Goldberg's conjecture. If $G$ is an edge-$k$-critical graph with $k\geq\Delta+1$, then, for every $e\in E(G)$, the edge set $E(G)-e$ can be partitioned into disjoint near-perfect m…

All graphs are finite and simple. A graph is $k$-critical if its chromatic number is $k$ and every proper subgraph is $(k-1)$-colorable. Let $g_k(n)$ be the largest integer…

Minimum-degree conjecture. Every 5-critical graph in ${\cal C}$ contains a vertex of degree four.

For an integer $\ell\geq 2$, call a graph $G$ $K_{\ell}$-critical if it contains a copy of $K_{\ell}$, is vertex-critical, and removing the vertex set of any copy of $K_{\ell}$ red…

Let $n\beq 7$, and let a $\mathbb{Z}_3$-flow-critical graph be a connected graph with no nowhere-zero $\mathbb{Z}_3$-flow such that contracting any edge produces a graph with a now…

A graph is 4-critical if it is not 3-colorable, but every proper subgraph is 3-colorable. Gallai's conjecture. Every 4-critical planar graph has average degree less than $4$. Koest…

Cichacz–Suchan's conjecture. The graph $\widehat{G}_{n,m}^{\lceil a\rceil}$ is $k$-critical-bipartite. This means that after the removal of any $k$ vertices from $U$, every vertex…

Keevash–Saks–Sudakov–Verstraëte conjecture. Suppose $k\ge h$ and $n$ is sufficiently large. Then

Su's conjecture. The graph $G$ has an edge that is contained in at most one clique $K_{k-1}$.

Abbott–Zhou conjecture. One has

Let $G$ be a finite simple graph. Its maximum degree is denoted by $\Delta(G)$, and its chromatic index by $\chi'(G)$. The graph $G$ is $k$-critical if $\Delta(G)=k$,…

Let $G$ be a $C_7$-critical graph on $n$ vertices, meaning that $G$ has no homomorphism to the cycle $C_7$, whereas every proper subgraph of $G$ does. Postle–Schaefer conjecture. T…

A graph $G$ is 4-critical if it is $4$-colourable but every proper subgraph is $3$-colourable; it is triangle-free if it contains no subgraph isomorphic to $K_3$. Write…

Let $G$ be a $Delta$-critical graph of order $n$, meaning that $G$ is critical of class 2 and $Delta(G)=Delta$. Call $G$ just overfull if … The Just Overfull Conjecture. If…