13 problems

Let $P_7$ denote the path on seven vertices and let $C_3$ denote the cycle on three vertices. A graph is 4-vertex-critical if its chromatic number is $4$ and deleting any vertex lo…

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 $\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…

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 $\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$.

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…