183 problems

Let $G$ be a bridgeless cubic graph, and let $P_{10}$ denote the Petersen graph. An $H$-coloring of a cubic graph $G$ is a mapping $f:E(G)\rightarrow E(H)$ such that for every vert…

Aharoni–Berger's conjecture.

Graham's conjecture. For every triangle $T$,

Let $K_n$ be the complete graph on $n$ vertices. An edge-coloring is proper if any two edges sharing a vertex receive distinct colors. Andersen's conjecture. Every proper edge-colo…

Let $c_q(G)$ denote the number of proper $q$-colorings of a graph $G$. Let $G$ be an $n$-vertex $d$-regular graph, with $q\ge 3$, and let $K_{d,d}$ be the complete bipartite graph…

Unfriendly Partition Conjecture.

Let $K_p$ be the complete graph on $p$ vertices, and let $f(n,H)$ be the smallest number of colors in an edge coloring of $K_n$ in which every copy of $H$ intersects at least one c…

Lazebnik's conjecture. For all $n \geq r \geq 2$ and $q \geq r$, the Turán graph $T_r(n)$ is the only graph on $n$ vertices and $t_r(n)$ edges that attains the maximum number of…

Second-range formula conjecture. Then

Let $H$ be a graph. Say that $H$ is common if a random two-coloring minimizes the density of monochromatic copies of $H$ in the complete graph $K_n$ among all two-colorings of the…

Stanley's e-positivity conjecture. If $G$ is a claw-free incomparability graph, then $X_G$ is e-positive; equivalently,

Let $G$ be a connected graph of chromatic number $k$, with $G\not\cong C_7$, where $C_7$ is the cycle of order $7$. A full $f$-rainbow path is a path whose vertices receive pairwis…

Frieze–Krivelevich conjecture. There exists a constant $\alpha>0$ such that every globally $\alpha n$-bounded coloring contains any spanning tree with bounded maximum degree.

Shearer's conjecture. For every two integers $s$ and $k$, there exists an integer $n_0$ such that, if $n\ge n_0$ and $G$ is an $n$-vertex graph with at most $sn$ cherries, then any…

The fall chromatic number equality conjecture. The equality

Reduction conjecture. For each positive integer $r$, there is a positive integer $j_r$ such that one of the cited theorems may be used to solve or bound $g(m,r)$.

Let $H$ be a graph that is $k$-colorable. For a finite graph $G$, let ${\rm Hom}(G,H)$ denote the space of graph homomorphisms from $G$ to $H$, with adjacency given by changing one…

Let $G$ be a graph of maximum degree $Delta$, let $delta\in(0,1)$, and consider the paper's particle-system algorithm for sampling independent sets with prescribed marginals. Exten…

Let $H$ be a graph, let $Delta(H)$ denote its maximum degree, and let $q$ be a positive integer. Optimal-mixing conjecture. Glauber dynamics for proper $q$-colorings of $H$ should…

Bradač–Liu–Wu–Xu conjecture. For every integer $k\geq 1$,

Let $S_{10}$ and $S_{12}$ be the cubic graphs defined in the source, and let an $H$-coloring of a cubic graph $G$ mean a mapping $f:E(G)\rightarrow E(H)$ such that for each vertex…

Let $G$ be a bridgeless graph, not necessarily cubic. An even subgraph is a subgraph in which every vertex has even degree. $(5,2)$-even-subgraph-cover conjecture. The graph $G$ co…

Let $M(H,n)$ be the minimum number of monochromatic copies of a graph $H$ in a red/blue coloring of $K_n$, and define the threshold Ramsey multiplicity by … where $r(H)$ is the Ram…

Let $H$ be a graph and let $M(H,n)$ be the minimum number of monochromatic copies of $H$ in a red/blue coloring of the edges of $K_n$. Erdős's conjecture. For every complete graph…

Three-color majority conjecture for finite digraphs.