187 problems

Dijoin additivity conjecture. The equality

Let $\gamma>0$ be a positive real number. In the word RAM model with word size $O(\log n)$ bits, consider algorithms deciding whether a graph with $m$ edges contains a triangle. Tr…

Consider Arc-Kayles played on subdivided stars with three paths, one of which has size $1$. Fix the length of the second path and vary the length of the third path, obtaining a seq…

Bermond et al.'s conjecture. The problem $(k,k)$-BLFD is NP-complete for all $k \geq 2$.

For a random multidigraph on $n$ vertices with geometric outdegree distribution, independently assign each vertex $v$ a geometrically distributed outdegree $d^+(v)$ with mode $0$ a…

Let $G$ be a graph and let $k$ node pairs $(s_1,t_1),\dots,(s_k,t_k)$ be given. The $k$-Disjoint Shortest Paths ($k$-DSP) problem asks for node-disjoint shortest paths…

Dynamic programming conjecture. A dynamic programming approach similar to the one used on trees can be used on graphs with treewidth $2$.

Complete-graph degree sequence optimization conjecture. The line sum problem over $H=K_{m,n}$, as well as the degree sequence optimization problem over $H=K_n$, is polynomial-time…

Bartha's conjecture. The unique perfect matching of $G$ can always be found in $O(m)$ time.

A graph property is CMSOL-definable if it can be expressed by a sentence in counting monadic second-order logic, and it is recognizable if it can be recognized by a finite-state tr…

Bauer et al.'s conjecture. Determining $\alpha_{\min}(d)$ is computationally hard. The same computational hardness is believed to hold for determining $\gamma_{\max}(d)$, where…

Let $FG$ be a Fibonacci graph, let $Ex(FG)$ be its associated algebraic expression, and measure a representation by the total number of terms and the number of plus operators. The…

Let $k_{\rm max}\ge 3$ be a finite integer, and consider random graphs in which every vertex has degree in $[3,k_{\rm max}]$. A graph is Hamiltonian if it contains a cycle of lengt…

Let $g$ be a specified graph and $G$ a larger graph. Represent them by rigid simplexes $s$ and $S$, respectively, and dynamically dock these simplexes during the proposed physical…

Let $G$ be a graph, and let $\Delta(G)$ denote its maximum degree and $\chi'(G)$ its chromatic index. Chetwynd–Hilton's algorithmic conjecture. There is a polynomial-time algorithm…

Let $(G,R)$ be an annotated graph, let $k$ be the number of terminal pairs, and write … Here $f$ denotes a computable function, and $|G|$ denotes the size of $G$. XP tractability c…

Lima, Milanič, Muršič, Okrasa, Rzążewski, and Štorgel's conjecture. For every fixed $r$ and formula $\psi$, $(\operatorname{tw} \leq r,\psi)$-MWIS can be solved in polynomial time…

Gartland and Lokshtanov's conjecture. For every fixed $r$ and CMSO$_2$ formula $\psi$, $(\operatorname{tw} \leq r,\psi)$-MWIS and $\operatorname{lcol}(3)$ can be solved in polynomi…

Exponential lower-bound conjecture. There is an exponential lower bound for the runtime of that algorithm.

Let $S$ be a semicomplete digraph, meaning that for every pair of distinct vertices $u,v\in V(S)$, at least one of $uv$ and $vu$ is an arc of $S$. Write…

Let $\mathscr C$ be a hereditary class of graphs. A class is dependent if it has the model-theoretic non-independence property, and first-order model checking is fixed parameter tr…

Finite-certificate conjecture. A finite extension of the O3/O6 certificate library should give depth $k+O(1)$ for three faults while preserving the minimum possible repair cost of…

The Hamming weighted clique problem asks whether a complete graph whose edge weights are Hamming distances between binary sequences contains a clique satisfying the specified size…

Let $V$ be a tournament with $n$ vertices, and let $U=V^*$ be a disjoint inversion tournament. Add a new vertex $w$, orient every edge from $U$ to $w$ and from $w$ to $V$, and cons…

Bonnet–Duron's conjecture. Every class of graphs with bounded stretch-width has clique-width at most logarithmic in the number of vertices; equivalently, there is a constant $c$ su…