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

Let $G=(V,E)$ be a finite simple graph with $n=|V|$ vertices and no isolated vertices. An odd induced subgraph is an induced subgraph in which every vertex has odd degree, and let…

Dallard et al.'s conjecture. Such graphs have bounded tree-independence number; equivalently, they admit tree decompositions whose bags induce subgraphs of bounded independence num…

Erdős–Palka conjecture. For every $C>1$, with high probability $G(n,C/n)$ contains an induced tree of linear size.

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…

Induced maximal outerplane subgraph conjecture.

For positive integers $n,s$, let $K_{s,s}$ be the complete bipartite graph with $s$ vertices in each part. For a graph $H$, let $\mathrm{ex}(n,H)$ be the maximum number of edges in…

Fox–Sudakov conjecture. Every graph $H$ has the polynomial Rödl property.

Let $d$ be a positive real number, and let $G$ be a triangle-free graph with minimum degree at least $d$. An induced bipartite subgraph of $G$ is a bipartite subgraph induced by a…

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

Narayanan–Sahasrabudhe–Tomon conjecture. When $m=k^2$, the graph $K_{k,k}$ is extremal for the number of different edge sizes of induced subgraphs among bipartite graphs with $m$ e…

Let $f(k)$) be the least integer such that every graph with more than $f(k)$ vertices has an induced regular subgraph with at least $k$ vertices. Erdős, Fajtlowicz and Staton conje…

Let $r\geq 2$, and let $G$ be an $((r-1)n+1)$-regular graph on $rn$ vertices. A subset of $V(G)$ induces a $K_r$-factor when the graph induced by that subset contains a vertex-disj…

Dominating Hadwiger's Conjecture. For every integer $t\geq 1$, every graph with no dominating $K_t$ minor is $(t-1)$-colorable.

Let $c>0$ be a constant, let $H$ be a fixed graph, and let a graph be $(c,t)$-sparse if every pair of subsets $A,B$ of its vertex set with $|A|,|B|\geq t$ has at most $(1-c)|A||B|$…

Let $G$ be a graph on $n$ vertices, and let $\b5(G)$ denote the number of non-isomorphic induced subgraphs of $G$. For a constant $c_1>0$, call $G$ $c_1$-Ramsey if it has no subset…

Let $\mathcal{F}$ be a finite set of graphs, and let an $\mathcal{F}$-free graph be a graph with no induced subgraph isomorphic to a member of $\mathcal{F}$. Let $\mathcal{S}$ be t…

Let $H$ be a fixed graph, and consider graphs $G$ in which every vertex set of size $|V(H)|$ induces $H$ with the correct count expected in the quasirandom model. Simonovits–Sós co…

For a graph $G$, let … where $e(H)$ denotes the number of edges of $H$. An $n$-vertex graph is $C$-Ramsey if it has no homogeneous subgraph of size $C\log_2 n$. Erdős–McKay conject…

Korpelainen–Lozin–Razgon conjecture. If a hereditary class of graphs $\mathcal{G}$ is defined by a finite set of forbidden induced subgraphs, then $\mathcal{G}$ is well-quasi-order…

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

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…

Let $G$ be a graph. Let $f_{\mathrm{o}}(G)$ denote the maximum order of an induced subgraph in which every vertex has odd degree, and let $f_{\mathrm{oe}}(G)$ denote the minimum, o…

Let $G$ be a graph, let $s$ and $h$ be positive integers, and let $K_{s,s}$ and $K_h$ denote complete graphs. An induced $K_h$-subdivision is a subdivision of $K_h$ appearing as an…