22 problems

Let $H$ be a connected graph, and let $\operatorname{Forb}(H)$ denote the class of graphs with no induced subgraph isomorphic to $H$. A graph class is DOM-bounded if its graphs hav…

Let $P_t$ denote the $t$-vertex path and $K_{,}$ the complete bipartite graph with … . A graph is … or $K_{,}$. Path–biclique alpha-degeneracy conjecture. For every two positive in…

Let $P_t$ denote the $t$-vertex path and $K_{\ell,\ell}$ the complete bipartite graph with … , a graph is … or $K_{,}$. Path–biclique tree-independence conjecture. For every two po…

For $a,b\in\mathbb{N}$, let $K_{a,a}$ be the complete bipartite graph with $a$ vertices in each part, and let the $b$-vertex path be the path with $b$ vertices. Dallard–Krnc–Kwon–M…

Let $\mathcal{F}$ be a finite class of graphs, and let $\mathcal{F}$-free mean having no induced subgraph isomorphic to a member of $\mathcal{F}$. A multiclaw is a graph each compo…

Let $\mathcal{F}$ be a finite class of graphs. A graph is $\mathcal{F}$-free if it has no induced subgraph isomorphic to any member of $\mathcal{F}$. The class of all $\mathcal{F}$…

For a family $\mathcal{F}$ of graphs, a graph $G$ is $\mathcal{F}$-free if no induced subgraph of $G$ is isomorphic to a graph in $\mathcal{F}$. Let $P_r$ be the path with $r$ vert…

All graphs under consideration are finite and simple. A graph is ISK4-free if it contains no induced subdivision of $K_4$. Lévêque et al.'s 4-color conjecture. Every ISK4-free grap…

Bounded tree-independence conjecture. For any two positive integers $k$ and $t$, the class of $\{P_k,K_{t,t}\}$-free graphs has bounded tree-independence number.

Let $G$ be a graph, and let $\chi(G)$ and $\omega(G)$ denote its chromatic number and clique number, respectively. A graph is $(P_5,\mathrm{kite})$-free if it has no induced subgra…

Let $G$ be a graph, and let $\chi(G)$ and $\omega(G)$ denote its chromatic number and clique number, respectively. A graph is $(P_5,\mathrm{flag})$-free if it has no induced subgra…

A graph is $P_6$-free if it has no induced subgraph isomorphic to the path on six vertices. The $4$-colorability problem asks whether the vertices of a graph can be partitioned int…

Let $\mathcal{C}_t^*$ be the class of graphs with no induced $C_4$, diamond, theta, prism, even wheel, or $K_t$. Here $C_4$ is a cycle on four vertices, and the other names denote…

Let $\accentset{\leftrightarrow}{K}_2$ be the complete digraph on two vertices, let $S_2^+$ be the two-out-star, and let $\vec{K}_4^s$ be the unique strong tournament on four verti…

Let $\accentset{\leftrightarrow}{K}_2$ be the complete digraph on two vertices, let $S_2^+$ be the orientation of a two-leaf star with all arcs directed outwards, and let…

An oriented graph is a digraph with no digons, and its dichromatic number $\vec{\chi}(D)$ is the least number of acyclic sets partitioning its vertex set. A digraph is a heroic set…

Dichotomy conjecture. There is a finite number of $k$-vertex-critical $H$-free graphs if and only if $H$ is an induced subgraph of $P_4+sP_1$ for some $s\geq 0$.

Polynomial-time DIM conjecture. For every fixed $i,j,k$, DIM is solvable in polynomial time for $S_{i,j,k}$-free graphs; in particular, this includes $P_k$-free graphs for…

Hertz et al.'s conjecture. The Independent Feedback Vertex Set problem should be polynomial-time solvable for $H$-free graphs whenever $H$ is a forest and each connected component…

Let $G$ be a co-bipartite unit disk graph, meaning that its vertex set can be partitioned into two cliques, and let the bipartite complement of $G$ be the graph obtained by complem…

Let $G_7$ be the strongly chordal graph described in the paper that is not a leaf power, and let a forbidden induced subgraph of leaf powers mean a graph that is not a leaf power b…

Let $\mathcal{G}$ be the class of all graphs with no induced four-edge path or four-edge antipath. A graph is prime if it has no nontrivial homogeneous set; a vertex is simplicial…