122 problems

For $0\leq m\leq k$, define … Thus $\chi_0(k;K_n)=\omega(k;K_n)$ and $\chi_k(k;K_n)=\chi(k;K_n)$. Mixed decomposition conjecture. Let $m$ and $n\geq 1$ be non-negative integers. Th…

A $k$-decomposition of the complete graph $K_n$ is a decomposition into $k$ spanning subgraphs $G_1,\ldots,G_k$, and for a graph parameter $p$ let … Here $\chi$ denotes chromatic n…

Let $G$ be a finite graph and let $t\in\mathbb{N}$. A minor of $G$ is a graph obtainable from $G$ by a sequence of vertex deletions, edge deletions, and edge contractions; write…

Let $d\text{-degenerate}$ graphs be graphs in which every subgraph has a vertex of degree at most $d$, and let $\chi_o(G)$ denote the oriented chromatic number of a graph $G$. For…

Erdős–Lovász–Tihany Conjecture. If

Typical-norm dense-coloring conjecture. For a typical norm,

Let $T$ be a forest, and let a graph be $T$-free if it has no induced subgraph isomorphic to $T$. A hereditary graph class is chi-bounded if there is a function…

All graphs considered are finite, simple, and undirected. For a graph $G$, let $\chi(G)$ denote its chromatic number, $\omega(G)$ its clique number, and $\Delta(G)$ its maximum deg…

Let $G$ be a graph, with maximum degree $\Delta(G)$ and clique number $\omega(G)$. Reed's conjecture. Every graph $G$ satisfies … This refines the Borodin–Kostochka direction and i…

Let $G$ be a graph with independence number $\alpha(G)=2$, let $\chi(G)$ denote its chromatic number, and let $K_{\chi(G)}$ be the complete graph on $\chi(G)$ vertices. A weak imme…

Let $G$ be a graph, let $\chi(G)$ denote its chromatic number, and let $K_{\chi(G)}$ be the complete graph on $\chi(G)$ vertices. A strong immersion of a graph $H$ in $G$ consists of…

Wu–Xu–Xu conjecture. Every graph in $\bigcup_{\ell\geq 2}{\cal H}_{\ell}$ is $3$-colorable.

Let $G_{n,p}$ be the random graph on $n$ vertices, let $G_{n,p}^r$ denote its $r$th power, and write $\chi(G)$ and $\alpha(G)$ for the chromatic and independence numbers of a graph…

Odd Hadwiger conjecture. If

Let $G$ be a graph, let $\chi(G)$ and $\omega(G)$ denote its chromatic and clique numbers, let $\chi_f(G)$ denote its fractional chromatic number, and let $H$ be a largest induced…

Let $W_t$ be the join of the cycle $C_t$ with $K_1$, let $\alpha(G)$ be the independence number of $G$, and let $G\Box H$ denote the Cartesian product of graphs. For $t\geq 2$, con…

Let $G$ be a non-empty graph with $m$ edges, chromatic number $\chi$, and least adjacency eigenvalue $\lambda_n$. The spectral edge-count conjecture. … This conjecture is motivated…

Let $k$ be an integer, let $G$ be a graph with at least $k$ vertices, and let $X$ be one side of a cut of $G$. Write $V(G)$ and $E(G)$ for the vertex and edge sets, and let…

Let $G$ be an $n$-vertex graph. A bipartite cut is a cut whose induced subgraph on one side is bipartite. Bogdanov–Neustroeva–Sokolov–Volostnov–Russkin–Voronov conjecture. Any $n$-…

Let $n,k$ be positive integers with $k\geq2$, and let $\vec{s}=(s_1,\ldots,s_k)$ be a positive integer vector with $s_i\geq2$ for $1\leq i\leq k-1$. Let…

Let $[n]=\{1,\ldots,n\}$, and let $\mathrm{KG}^r(n,k)_{s\textup{-stab}}$ be the induced $r$-uniform Kneser hypergraph whose vertices are the $s$-stable $k$-subsets of $[n]$, where…

Let $r(G)$ be the maximum chromatic number of a subgraph spanned by an odd cycle of a graph $G$, and let $\chi(G)$ be the chromatic number of $G$. Linear separation conjecture. For…

Let $G$ be a graph, and let $r(G)$ denote the maximum chromatic number of a subgraph spanned by an odd cycle of $G$, while $\chi(G)$ denotes the chromatic number of $G$. Gyárfás' b…

Independence-number lower-bound conjecture. For any graph $G$,

Chromatic lower-bound conjecture. For any graph $G$,