39 problems

For a graph $G$, let $\chi(G)$ denote its chromatic number and let $\omega(G)$ denote its clique number. A graph is $P$-free if it contains no induced copy of the path $P$. Path-fr…

A hole is an induced cycle of length at least four, and a graph is even-hole-free if it has no hole of even length. For a graph $G$, let $\chi(G)$ denote its chromatic number and…

Let $T$ be a forest, and let a graph be $T$-free if it has no induced subgraph isomorphic to $T$. A hereditary graph class is chi-bounded if there is a function…

A poset tournament is a tournament $T$ for which there exists a total ordering $<$ of $V(T)$ such that, for all $u<v<w$, if $u\to_T v$ and $v\to_T w$, then $u\to_T w$. Equivalently…

Let $\mathcal{C}$ be a class of tournaments, where a tournament is an orientation of a complete graph. Let $\mathcal{C}^{subst}$ denote the closure of $\mathcal{C}$ under substitut…

Let a hole be a chordless cycle of length at least four; it is even if its length is even. For an integer $k\geqslant 2$, a graph $G$ with at least one edge is $k$-divisible if, fo…

Ramsey-type bound conjecture. For every $\chi$-bounded class $\mathcal G$ and every two integers $m,s\ge1$, there exists $C=C(\mathcal G,m,s)\ge1$ such that every $\overline{mK_s}$…

Cocktail-party-free subclass conjecture. For every integer $m\ge1$, the $\overline{mK_2}$-free subclass of every $\chi$-bounded class is linearly $\chi$-bounded.

C4-free subclass conjecture. The $C_4$-free subclass of every $\chi$-bounded class is linearly $\chi$-bounded.

Let $H$ be a forest, and let $G$ be an $H$-free graph, meaning that $G$ has no induced subgraph isomorphic to $H$. Write $\chi(G)$ for its chromatic number and $\omega(G)$ for its…

Let $\mathcal{G}$ be a hereditary graph class, and suppose it is $\chi$-bounded: there is a function $g$ such that $\chi(G)\leq g(\omega(G))$ for every $G\in\mathcal{G}$. Esperet's…

Esperet's conjecture. Every chi-bounded hereditary class is poly-chi-bounded.

A graph class is Burling-controlled when its chromatic complexity is controlled by the Burling graphs, as defined in the source. An induced subdivision of a graph $F$ is a subdivis…

Five-holed graph chromatic bound conjecture. If $G$ is $5$-holed, then

A graph $G$ is fork-free if it has no induced subgraph isomorphic to the graph obtained from $K_{1,3}$ by subdividing one edge once. A graph is perfectly divisible if, for each ind…

Let $G$ be a finite simple graph. For a vertex $v\in V(G)$, write $N_G[v]=N_G(v)\cup\{v\}$, and call $G$ $\varepsilon$-colourful if … for every $v\in V(G)$. For an induced subgraph…

Let $G$ be a finite simple graph. For disjoint vertex sets $A,B\subseteq V(G)$, call $(A,B)$ a complete pair if every possible edge between $A$ and $B$ is present. For a forest $T$…

Linear-forest conjecture. If $H$ is a linear forest, then the class of $H$-free graphs is intersectionwise self-$\chi$-guarding.

Fix a positive integer $d$, and let $\mathcal{B}_d$ be the class of intersection graphs of axis-aligned boxes in $\mathbb{R}^d$. A hereditary class is Pollyanna if every hereditary…

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…

Chi-boundedness conjecture. For any two integers $k,c\in\mathbb{N}$ there exists an integer $r$ such that every graph with induced matching treewidth at most $k$ and clique number…

Let $T$ be a tournament and suppose that one of its backedge graphs is a forest. For a tournament, let its clique number mean the minimum clique number of a backedge graph over all…

Tournament Gyárfás–Sumner conjecture. If $T$ has a backedge graph that is a forest, then the class of tournaments not containing $T$ as a subgraph is dichromatically bounded by cli…

An ordered graph is a graph together with a total vertex ordering. The ordered matching conjecture. Let $(M,\prec)$ be an ordered graph with maximum degree $1$. Then the class of…

For a graph $G$, let $\chi(G)$ denote its chromatic number and $\omega(G)$ its clique number. A graph is $P_5$-free if it has no induced subgraph isomorphic to the five-vertex path…