66 problems

Everett–Reed's conjecture. A graph $G$ is perfectly contractile if and only if $G$ contains no odd holes, no antiholes, and no odd prisms as induced subgraphs.

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$, write $\rho(G)$ for its chromatic number and $\tau(G)$ for its clique number. A graph is minimally nonperfectly divisi…

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…

Let $G$ be a minimally imperfect graph, meaning a graph that is imperfect while every proper induced subgraph is perfect. A partition antisymétrique is a partition of $V(G)$ into s…

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…

Maffray–Thomas conjecture. Every bipartisan graph is a quasi-parity graph.

Strong Perfect Graph Conjecture. A graph is perfect if and only if it does not contain as an induced subgraph an odd hole or an odd antihole of length at least $5$.

Let $G$ be a Berge graph, that is, a graph with no odd hole and no odd antihole. Let $\overline{G}$ denote its complement, let a 2-join be the decomposition defined earlier in the…

Perfect-contractility conjecture. The following conditions are equivalent:

Let $P_t$ denote the path on $t$ vertices and let $K_k$ denote the complete graph on $k$ vertices. A graph is polynomial-bounded by $k$ if its chromatic number is bounded by a poly…

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 partitioned probe graph is a graph $G$ whose vertex set is partitioned into probes $P$ and non-probes $N$, such that adding edges among vertices of $N$ can produce a graph in the…

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:

Non-perfection conjecture. Every optimal $1$-planar graph with at least $10$ vertices is not perfect.

Colourability conjecture. Every $(\text{co-gem},\overline{C_5},\overline{C_7},\ldots,\overline{C_{2k-5}},K_k)$-free graph is $k$-colourable.

Let $G$ be a graph such that every finite induced subgraph of $G$ is perfect and $G$ has no infinite independent set of vertices. Aharoni's conjecture. The graph $G$ admits a verte…

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…