46 problems

Let $G$ be a $d$-degenerate triangle-free graph, and let $\chi_f(G)$ denote its fractional chromatic number. Harris's conjecture. One has … This conjecture was subsequently proved…

Let $G$ be a triangle-free graph with maximum degree at most $3$. Its fractional chromatic number $\chi_f(G)$ is the minimum of $a/b$ over all fractional $a/b$-colorings, where a f…

Let $G$ and $H$ be graphs, and let $g$ and $h$ be maximum fractional cliques of $G$ and $H$, respectively. A fractional clique is a map $f:V(G)\to[0,1]$ whose sum on every independ…

Let $\chi_f”(G)$ denote the fractional total chromatic number. Reed's conjecture. For every $\epsilon>0$ and every maximum degree $\Delta$, there exists a girth $g$ such that every…

Let $G$ be a planar graph of girth at least five, and let $\chi_f(G)$ denote its fractional chromatic number. Dvořák–Mnich conjecture. There exists a real number $c<3$ such that ev…

Let $d$ be sufficiently large, and let $G$ be a $d$-degenerate triangle-free graph with fractional chromatic number $\chi_f(G)$. Martinsson–Steiner conjecture. The following two as…

Kahn's conjecture. As the relevant degree parameters tend to infinity, the chromatic index of a $k$-uniform hypergraph is asymptotically equivalent to its fractional chromatic inde…

Let $H$ be an $r$-uniform $d$-degenerate triangle-free hypergraph, with $r\geq 3$. Here, $\chi_f(H)$ denotes the fractional chromatic number, and $c_r>0$ is a constant depending on…

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, let $\chi_f(G)$ be the fractional chromatic number, and let $\Box$ denote the Carte…

Let $W_t$ be the join of the cycle $C_t$ with $K_1$, let $\chi_f(G)$ denote the fractional chromatic number of a graph $G$, and let $W_{2t+1}^{\Box 2}$ be the Cartesian square of t…

Let $G$ be a planar graph, and let $a_f(G)$ denote its fractional arboricity: the minimum ratio $p/q$ for which vertices can be assigned at least $q$ colors from a total of at most…

Let $n$ tend to infinity, and let $G$ be a triangle-free graph on $n$ vertices. Write $\chi_f(G)$ for its fractional chromatic number. Cames van Batenburg–de Joannis de Verclos–Kan…

Let $G$ be a triangle-free graph, and let $d_G(v)$ denote the degree of a vertex $v\in V(G)$. Consider a probability distribution on the independent sets of $G$. Kelly–Postle's loc…

Let $\mathcal{L}=\{\mathcal{M}_1,\ldots,\mathcal{M}_k\}\in\mathcal{D}^k$ be matroids on $V$, let $\mathcal{C}=\bigcap\mathcal{L}$, and let $\vec h\in\mathbb{R}_{\ge0}^V$. Weighted…

Let $G$ be a 4-cycle-free planar graph, and let $\chi_f(G)$ denote its fractional chromatic number. Fractional chromatic conjecture. There exists some $\epsilon>0$ such that … The…

Let $G$ be an $n$-vertex planar graph of girth at least five, and let $\chi_f(G)$ denote its fractional chromatic number. Dvořák and Mnich's conjecture. There exists some…

Harris's conjecture. There is an absolute constant implicit in the $O$-notation such that

For positive integers $a$ and $b$, a graph is $(a:b)$-choosable if every assignment of lists of $a$ colors admits a $b$-fold list coloring. Zhu's conjecture. Every planar graph is…

For positive integers $a$ and $b$, a graph is $(a:b)$-choosable if, for every assignment $L$ of lists with $|L(v)|=a$ at each vertex $v$, it admits a $b$-fold $L$-coloring. Thresho…

Gimbel–Kündgen–Li–Thomassen conjecture. Every 4-chromatic planar graph has fractional chromatic number strictly greater than $3$.

Intermediate fractional colorability conjecture. Every such graph $G$ is fractionally $19/7$-colorable.

A graph has a $(a:b)$-coloring if each vertex receives a set of $b$ colors from a palette of $a$ colors, with adjacent vertices receiving disjoint sets. Let $k\geqslant 2$ and $q$…

Let $s$ be a positive integer, and let $G$ be a planar graph of girth at least $2s+2$. A fractional $(2s+1:s)$-coloring assigns to each vertex an $s$-element subset of a $(2s+1)$-e…

Let $G$ be a triangle-free subcubic graph, and let $F_{11}$, $F_{14}^{(1)}$, $F_{14}^{(2)}$, $F_{19}^{(1)}$, $F_{19}^{(2)}$, and $F_{22}$ be the six specified graphs. Let…