75 problems

All graphs considered are finite, simple, and undirected. For a graph $G$, let $\chi(G)$ and $\omega(G)$ denote its chromatic number and clique number. If $H$ is a graph, then $G$…

Gyárfás's conjecture. The family of odd-hole-free graphs, the family of graphs with no hole of length at least $\ell$, and the family of graphs with no odd hole of length at least…

Scott's conjecture. For every fixed graph $H$, the class of graphs containing no induced subdivision of $H$ is chi-bounded.

Let ${\mathcal C}$ be a hereditary graph class, and suppose that ${\mathcal C}$ is chi-bounded, meaning that its chromatic number is bounded by a function of its clique number. Esp…

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…

All graphs considered are finite and simple. For a graph $G$, let $\chi(G)$ be its chromatic number and $\omega(G)$ its clique number. A graph $H$ is an induced subgraph of $G$ if…

A graph is 4-holed if every hole in it has length $4$, where a hole is an induced cycle of length at least four. For a graph $G$, let $4chi(G)4$ denote its chromatic number and…

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 $G$ be a graph, and let $\chi(G)$ and $\omega(G)$ denote its chromatic number and clique number, respectively. A graph is $P_5$-free if it has no induced path on five vertices.…

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 an integer $k\geq 1$, let $\mathcal{C}_k$ be the class of graphs that contain no cycle with exactly $k$ chords. A family of graphs is chi-bounded if there is a function $f$ suc…

A point visibility graph is the graph associated with a finite set of points in the plane, with two points adjacent when they are visible to each other in the relevant geometric se…

Chen–Xu–Xu conjecture. If $q\ge 2$ and $G$ is a $(\mathrm{cap},\mathrm{even\\ hole})$-free graph with no odd hole of length at most $2q-1$, then

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…

Fix a graph $F$, and let ${\mathcal C}$ be a hereditary graph class. Say that ${\mathcal C}$ is chi-unbounded if its chromatic numbers are not bounded as a function of clique numbe…

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…

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…

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…

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