57 problems

Let $K_n$ be the complete graph on $n$ vertices, and define … Here $\operatorname{cr}(G)$ denotes the minimum number of crossings in a plane drawing of a graph $G$. Harary–Hill con…

Let $K_n$ be the complete graph on $n$ vertices, let $\sigma$ be a signature on $K_n$, and let $\chi ' (K_n, \sigma)$ denote its signed chromatic index. Chromatic-index conjecture.…

For each nonnegative integer $g\neq 2$, let … and let $S_g$ denote the orientable surface of genus $g$. A Kainen drawing is a drawing attaining Kainen's lower bound for the surface…

Separation-number conjecture. Under these conditions,

Graham–Kleitman conjecture. The quantity $f(K_n)$ is closer to the upper bound than to the lower bound. The source does not specify a precise quantitative formulation, and the stat…

Let $K_v$ be the complete graph on $\{0,1,\dots,v-1\}$, and define the edge length by … Let $L$ be a list of $v-1$ positive integers not exceeding $\lfloor v/2\rfloor$. Horak and R…

Let $K_5$ be the complete graph on five vertices. Complete-graph $K_5$ conjecture. … The source presents this as a conjectural computational pattern and gives no resolution.

Let $K_4$ be the complete graph on four vertices. Complete-graph $K_4$ conjecture. For every $m\geq4$, … The paper reports verification for $m\leq14$, but does not establish the st…

Let $K_n$ be the complete graph on $n$ vertices, and let $w^1_{{\mathcal A}_3}(K_n)$ denote the width of the torsion in $H^{1,*}_{{\mathcal A}_3}(K_n)$. Width conjecture for comple…

Buchanan et al.'s conjecture. For such $k$,

Let $K_a$ be a complete graph of order $a$ and $P_b^\mathrm{alt}$ an alternating path of order $b$. Complete-graph cyclic conjecture. For any $a, b \in \mathbb{N}$, we have … The c…

Let $K_a$ be a complete graph of order $a$ and $P_b^\mathrm{alt}$ an alternating path of order $b$. Complete-graph–alternating-path conjecture. For any $a \ge 2$ and $b \ge 3$, we…

Uniform connected subgraph p-NC conjecture. For every $n$ for which the measure is defined, $\mathbb{P}_{\mathrm{UC}}$ satisfies the p-NC property.

Ábrego et al.'s conjecture. For each positive integer $n$ multiple of $3$, there is an optimal rectilinear drawing of $K_n$ that is 3-symmetric and 3-decomposable.

Let $P_{\ell t}\Diamond_{\ell}K_6$ denote the path-aligned product of a path and the complete graph $K_6$, and let $\chi_p(G)$ be the packing chromatic number of a graph $G$. Twent…

Join zero conjecture. The polynomial $g_{K_{2+r}\vee\overline{K}_{s+r}}(t)$ has a zero of order $s$ at

Complete multipartite formula conjecture. Their Speyer polynomials are

For a rectilinear drawing of the complete graph $K_n$, let $e_k(K_n)$ denote the number of edges crossed exactly $k$ times, and let … denote the maximum of $e_k(K_n)$ over all rect…

Let $\delta_1(c)$ denote the minimum genus of a dual-separable embedding of a $c$-connected graph, and let $\gamma(K_{c+1})$ denote the genus of the complete graph $K_{c+1}$. Optim…

Fox, Grinshpun, and Pach's conjecture. For positive integers $k$ and $p$,

For a graph $G$, let $b_2(G)$ denote its biclique partition number over the field of two elements, and let $K_n$ denote the complete graph on $n$ vertices. Let $k$ be a positive in…

Buchanan–Clifton–Culver–Nie–O'Neill–Rombach–Yin conjecture. For every odd positive integer $n$,

Let $K_n$ be the complete graph on $n$ vertices. In a general edge-coloring of $K_n$, let $\tau_s(n)$ denote the minimum number of colors needed so that all triangles have distinct…

Let $K_n$ be the complete graph on $n$ vertices, and let $\tau_m(n)$ denote the minimum number of colors in an edge-coloring of $K_n$ such that all triangles have distinct color pa…

Let $K_{4n+1}$ be a complete graph on $4n+1$ vertices, where … and both $m_1$ and $m_2$ are even. A graphical pair $((G,g),(H,h))$ without loops consists here of graphs $G$ and $H$…