110 problems

Let $G$ be a finite simple graph, let $f_o(G)$ be the maximum order of an induced subgraph of $G$ whose every vertex has odd degree, and let $\chi(G)$ be the chromatic number of…

Let $H$ be a fixed forest, and let $\mathcal{G}(H)$ denote the hereditary class of graphs with no induced subgraph isomorphic to $H$. A graph class is chi-bound if there is a funct…

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…

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…

Let $G$ be a $3$-connected graph. A set $W\subset V(G)$ is contractible if $G(W)$ is connected and $G-W$ is $2$-connected; a contractible set with $k$ vertices is called a $k$-cont…

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…

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

Induced maximal outerplane subgraph conjecture.

Caro's conjecture. There exists a positive constant $c$ such that every $n$-vertex graph without isolated vertices contains an odd induced subgraph with at least $cn$ vertices.

Plummer–Zha's conjecture. Every pentagraph is $3$-colorable.

Let $k\geq 3$, and let $h_k(n)$ denote the number of induced copies of $C_{2k+1}$ obtained by evenly blowing up $k$ pairwise non-adjacent vertices in a $C_{2k+1}$ on $n$ vertices.…

Gyárfás–Sumner analogue for $\eta$-boundedness. For every forest $H$, there exists a function $f:\mathbb{N}\to\mathbb{N}$ such that every $H$-free graph $G$ satisfies…

Conjecture. There exists a constant $n_s$ depending on $s$ such that $G$ is not uniquely Hamiltonian whenever $n\geq n_s$.

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

Let $P_6$ be the path on six vertices, and let ${\mathrm{ex}}_{\mathcal P}(n,P_6^{\mathrm{ind}})$ be the maximum number of edges in an $n$-vertex planar graph containing no induced…

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

Let $G$ be a graph. A graph is perfectly divisible if, for every induced subgraph $H$, the vertex set $V(H)$ can be partitioned into sets $A$ and $B$ such that $H[A]$ is perfect an…

Let $G$ be a graph and let $X,Y\subseteq V(G)$. An $(X,Y)$-path is a path with one endpoint in $X$ and the other in $Y$, and two paths are anti-complete if they are vertex-disjoint…

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 $G$ be a graph on $n$ vertices with $m$ edges, and let $\alpha_1(G)$ denote the order of a largest induced $1$-degenerate subgraph of $G$, equivalently a largest induced forest…

For a graph $G$ with $n$ vertices and genus $g$, let $\alpha_1(G)$ denote the order of a largest induced $1$-degenerate subgraph of $G$, equivalently a largest induced forest. Half…

Let $\alpha_d(k)$ denote the infimum, over $k$-degenerate graphs, of the ratio of the order of a largest induced $d$-degenerate subgraph to the number of vertices. Induced-degenera…

A wheel is a graph consisting of an induced cycle of length at least $4$ and one additional vertex adjacent to at least three vertices on the cycle. A graph class is Burling-contro…

Let $G$ be a finite graph, let $T$ be a forest, and write $\chi(G)$ for the chromatic number and $\omega(G)$ for the clique number. Polynomial Gyárfás–Sumner conjecture. For every…

Induced Menger conjecture. There exists a function $f:\mathbb{N}^2\rightarrow\mathbb{N}$ such that there exists either $k$ pairwise non-adjacent $A$-$B$ paths, or a separator $S$ b…