7 problems

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…

An odd subdivision of a graph $G$ is a graph obtained from $G$ by replacing each edge by a path of odd length. For a positive integer $s$, a graph is $K_{s,s}$-free if it contains…

For a graph $H$, an odd subdivision is a subdivision in which every replacing path has an odd number of edges. Scott–Seymour's conjecture. For every graph $H$ and integer $t$, the…

Here graphs are simple and finite. A graph is triangle-free if it contains no triangle and ISK4-free if it contains no induced subdivision of $K_4$, where $K_4$ is the complete gra…

A graph is ISK4-free if it has no induced subdivision of $K_4$. ISK4-free four-color conjecture. Every ISK4-free graph is 4-colorable. The preceding theorem gives a constant bound…

Monotonicity conjecture. If $i_D$ (respectively, $i'_D$) is NP-complete, then for every digraph $D'$ containing $D$ as an induced subdigraph, $i_{D'}$ (respectively, $i'_{D'}$) is…

Induced-subdivision dichotomy conjecture. $i_D$ is NP-complete unless $D$ is the disjoint union of spiders and at most one $2$-cycle.