32 problems

Let $G$ be a finite, undirected, loopless simple graph, let $|G|$ denote its number of vertices, let $\Delta=\Delta(G)$ be its maximum degree, and let $\overline{d}(G)$ be its aver…

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…

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 $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 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…

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…

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

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

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…

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…

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…

Dvořák–Postle conjecture. If $G$ is $C_5$-critical, then

Postle's density conjecture. For every $k\geq 4$, there exists $\varepsilon_k>0$ such that if $G$ does not contain a $K_{k-2}$ subgraph, then

Let $d$ be any integer, let $k_d$ be a threshold depending on $d$, and let ${\rm SG}(2k+d,k)$ be the Schrijver graph. An edge is interlacing according to the standard interlacing-e…

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$…

Potential-function conjecture. For every $k\geq 6$, there exist $\varepsilon_k,\delta_k,P_k>0$ such that the $(\varepsilon_k,\delta_k)$-potential satisfies

Let $k$ be an integer with $k\geq 4$, and let $G$ be a $k$-critical graph, meaning that $\chi(G)=k$ and every proper subgraph of $G$ has chromatic number less than $k$. Let…

A graph is $k$-crossing-critical if its crossing number is at least $k$ while deleting any edge reduces the crossing number below $k$. Let $g:\mathbb N\to\mathbb R^+$ be a function…

Barrus–Sinković conjecture. $G$ has maximum degree at most

Dvořák–Giannopoulou–Thilikos conjecture. $G$ has at most

For integers $k\geq 1$ and $n\geq 2k+1$, let $QG(n,k)$ be the spanning subgraph of the Schrijver graph $SG(n,k)$ constructed in Theorem 1.1, which is a quadrangulation of…

Edge-density conjecture. For every $k\ge 4$, there exists $\epsilon_k>0$ such that if $G$ is a $k$-critical $K_{k-2}$-free graph, then

A graph is planar if it can be embedded in the plane without crossings. A graph is 4-critical if its chromatic number is 4 and deleting any edge lowers its chromatic number. A grap…

The density conjecture for $5/2$-critical graphs. If $G$ is a $5/2$-critical graph, then