44 problems

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…

Let $G$ be a graph with no induced odd cycle of length at least five. A graph is perfectly divisible if, for every induced subgraph $H$ with at least one edge, its vertex set can b…

Kempe-equivalence conjecture. The graph $G$ is perfectly contractile if and only if, for every replication graph $H$ of an arbitrary induced subgraph of $G$ and every…

Let $D$ be a digraph. A stable set is a set of pairwise non-adjacent vertices, and a path partition is a collection of disjoint paths containing every vertex of $D$ exactly once. A…

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…

Let $G$ be a graph. A graph is normal if its vertex set has coverings by cliques and by independent sets such that every clique in the first covering intersects every independent s…

De Simone–Körner conjecture. A graph $G$ is hereditarily normal if and only if neither $G$ nor its complement contains a 5-cycle or a 7-cycle as an induced subgraph.

Let $G$ be a finite simple graph. A Berge graph is a graph containing neither an odd hole nor the complement of an odd hole. A graph is basic if it belongs to one of the four class…

Let $G$ be a finite simple graph. A minimally imperfect graph is a graph that is not perfect but whose proper induced subgraphs are all perfect. A hole is a chordless cycle of leng…

All graphs considered are finite and simple. For a graph $G$, write $\rho(G)$ for its chromatic number and $\tau(G)$ for its clique number. A graph is minimally nonperfectly divisi…

Perfect-contractility conjecture. The following conditions are equivalent:

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 $P_6$, $G_4$, and $G_5$ be the graphs described in Figure 5 of the source. Puech's conjecture. If $G$ does not contain $P_6$, $G_4$, or $G_5$ as induced…

A graph is $P_5$-free if it has no induced subgraph isomorphic to the path $P_5$. Faudree–Favaron–Li conjecture. Any $P_5$-free graph is irredundance perfect. Puech proved this con…

Let $G$ be a graph, and let $P_6$, $G_1$, and $G_2$ be the graphs described in Figure 5 of the source. Favaron's conjecture. If $G$ does not contain $P_6$, $G_1$, or $G_2$ as induc…

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 $H$ be a graph, let $K_2$ be the complete graph on two vertices, and let $k\in\mathbb{N}_{>2}$. Assume that every $H$-free graph is perfectly $(k-2)$-divisible. The H-union-K2…

Stable-set ideal conjecture. The following conditions are equivalent:

A graph is perfectly divisible if, for every induced subgraph $H$, its vertex set can be partitioned into $A$ and $B$ such that $H[A]$ is perfect and $\omega(H[B])<\omega(H)$. A fo…

Authors–Shibata conjecture. The following conditions are equivalent:

Aharoni–Lovász conjecture. Every perfect graph in which all independent sets are finite is strongly perfect.

Induced 5-hole conjecture. There exists a subset $X$ of $G$ such that the subgraph of $\Gamma(G)$ induced by $X$ is a 5-hole.

Non-perfectness conjecture. The generating graph $\Gamma(G)$ is not perfect.

Let $G$ be a graph. A graph is strongly perfect if every induced subgraph has a stable set meeting every nonempty maximal clique. An odd hole is an induced cycle of odd length, and…

Let $G$ be a graph. It is minimally $\gamma_g$-imperfect if $G$ is not $\gamma_g$-perfect, while every proper induced subgraph of $G$ is $\gamma_g$-perfect. The anti-holes…