39 problems

Let $G$ be a finite simple graph, let $c\geq 4$, and let $\operatorname{mad}(G)$ be its maximum average degree, defined by … An odd $c$-coloring is a proper $c$-coloring in which e…

Graph characterization conjecture. Then $(G,p)$ is generically minimally rigid on ${\mathcal{M}}$ if and only if $G=K_{2}$, $K_3$, $K_4$, or $G$ is $(2,1)$-tight.

Let $H$ be a fixed graph without isolated vertices. For $0<\beta<1$, let $\mathcal M_H(\beta)$ be the supremum of $t(H,W)$ over graphons $W$ with $t(K_2,W)\le\beta$. For…

Let $H$ be a fixed graph. For each vertex $x\in V(H)$, let $V_x$ be a pairwise disjoint set of $n$ vertices, and let $\mathcal G(H,n,m)$ be the family of graphs with vertex set…

Chen et al.'s conjecture. If $\theta(G)\ge 5$, then

Let $\mathscr C$ be a hereditary weakly sparse class of graphs. An internal tree-ordering expansion of a graph is an expansion by the forest-ordering defined by a spanning forest;…

Let $\mathscr C$ be a class of TOWS graphs, and let $\mathsf{Sp}(\mathscr C)$ be the class obtained by the paper's sparsifying transduction. Let $\Pi_S$ be a downset of weakly spar…

Li and Rousseau's conjecture.

Chernyshev–Rauch–Rautenbach conjecture. If $G$ has fewer than $3n-6$ edges, then $G$ has a forest cut.

Polynomial-expansion lower-bound conjecture. For every real $b>0$, there exists a graph class with expansion $O(r^b)$ such that for infinitely many $p\in\mathbb N$ the class contai…

Let $\Pi$ be a graph-class property. A hereditary weakly sparse class is a hereditary graph class excluding some biclique $K_{t,t}$ as a subgraph. Meta-conjecture-ws$(\Pi)$. Every…

Let $G$ be a graph of order $n$ and size $m$. Assume that $G$ is 3-connected and that every neighborhood of a vertex contains a cycle. Minimum-size conjecture. Then … The question…

Let $G$ be a finite, simple, undirected graph of order $n$, and call a vertex set a forest cut if it is a vertex cut whose induced subgraph is a forest. Forest-cut conjecture. If…

Let $H$ be a graph, and let $\mathcal{D}_H$ be the property of not containing a subdivision of $H$ as an induced subgraph. For a graph $\Gamma$, write…

Let $k$ and $d$ be positive integers. For a graph $G$, call it $(k,d)$-sparse if every subgraph $H$ satisfies … Call a subgraph $H$ $(k+1)$-overfull if $e(H)>(k+1)(v(H)-1)$. Sparse…

Let $G$ be a planar graph, and let $e$ and $f$ be edges added to $G$. A graph is $(3,6)$-tight if it has $3|V|-6$ edges and every subgraph $H$ with at least three vertices satisfie…

Let $\operatorname{tw}(G)$ denote the treewidth of $G$. The general sparse induced-subgraph conjecture. For every $t\geq 1$, every graph of sufficiently large treewidth has an indu…

Let $t\geq 4$ be an integer, let $H$ be a $2$-forest, and let an $(\mathcal{F})$-free graph mean a graph with no induced subgraph isomorphic to a member of $\mathcal{F}$. The bound…

Let $\mathcal{C}$ be a class of graphs of twin-width at most $3$, and suppose there exists an integer $t$ such that no graph $G\in\mathcal{C}$ contains $K_{t,t}$ as a subgraph. Spa…

Let $G$ be a finite simple graph, let $\operatorname{mad}(G)$ be the maximum of $\frac{2|E(H)|}{|V(H)|}$ over all non-empty subgraphs $H$ of $G$, and let $\chi_o(G)$ be the least p…

Let $\mathrm{mad}(G)$ denote the maximum average degree of $G$, and let $\chi_o(G)$ be the smallest number of colors admitting an odd coloring of $G$. Fix $\epsilon$ such that…

Independent packing conjecture. There exists an independent $C$-packing with contact graph $G$.

Sparsity conjecture. For $q\in(1,\infty)$ with $q\not=2$, and $d\geq 1$, a graph $G$ is independent in $\ell_q^d$ if and only if $G$ is $(d,d)$-sparse.

Let $\mathcal{C}$ be a nowhere dense class of graphs, let $d$ be a positive integer, and let $\varepsilon$ be a positive real. For a graph $G$, write $G^d$ for its $d$th power, and…

Let $G=(V,E,L)$ be a looped simple graph. For a positive integer $k$, let $G^{[k]}$ be the graph obtained by adding $k$ new loops at every vertex, and call $G$ $k$-tight if every v…