We consider Colouring on graphs that are $H$-subgraph-free for some fixed graph $H$, which are graphs that do not contain $H$ as a subgraph. To classify the complexity of Colouring on $H$-subgraph-free graphs for connected $H$, it remains to consider when $H$ is a tree of maximum degree $4$ with exactly one vertex of degree $4$, or a tree of maximum degree $3$ with at least two vertices of degree $3$. We let $H$ be a so-called subdivided ``H''-graph, which is either a subdivided $\mathbb{H}_0$: a tree of maximum degree $4$ that is a star, or a subdivided $\mathbb{H}_1$: a tree of maximum degree $3$ with exactly two vertices of degree $3$. We develop new decomposition theorems resulting in polynomial-time algorithms, and in combination with known results, fully classify all cases $\mathbb{H}_0$ and $\mathbb{H}_1$. To illustrate the wider applicability of our techniques, we also employ them to obtain similar new polynomial-time results for two other classic graph problems: Stable Cut and, in part, Feedback Vertex Set.

A graph is pseudo 2-factor isomorphic if all of its 2-factors have the same parity of number of cycles. Abreu et al. (2008) conjectured that K3,3 , the Heawood graph and the Pappus graph are the only essentially 4-edge-connected pseudo 2-factor isomorphic cubic bipartite graphs. This conjecture was disproved by Goedgebeur (2015) who constructed a coun- terexample G (of girth 6) on 30 vertices. Using a computer search, he also showed that this is the only counterexample up to at least 40 vertices and that there are no counterexamples of girth greater than 6 up to at least 48 vertices. In this manuscript, we show that the Gray graph – which has 54 vertices and girth 8 – is also a counterexample to the pseudo 2-factor isomorphic graph conjecture. Next to the graph G, this is the only other known counterexample. Using a computer search, we show that there are no smaller counterexamples of girth 8 and show that there are no other counterexamples up to at least 42 vertices of any girth. Moreover, we also verified that there are no further counterexamples among the known censuses of symmetrical graphs. Recall that a graph is 2-factor Hamiltonian if all of its 2-factors are Hamiltonian cycles. As a by-product of the computer searches performed for this paper, we have verified that the 2-factor Hamiltonian conjecture of Funk et al. (2003), which is still open, holds for cubic bipartite graphs of girth at least 8 up to 52 vertices, and up to 42 vertices for any girth.

Given two graphs H 1 and H 2 , a graph is ( H 1 , H 2 ) -free if it contains no induced subgraph isomorphic to H 1 or H 2 . A graph G is k -vertex-critical if every proper induced subgraph of G has chromatic number less than k , but G has chromatic number k . The study of k -vertex-critical graphs for specific graph classes is an important topic in algorithmic graph theory because if the number of such graphs that are in a given hereditary graph class is finite, then there exists a polynomial-time certifying algorithm to decide the k -colorability of a graph in the class. In this paper, we show that: (1) for k ≥ 1 , there are finitely many k -vertex-critical ( P 5 , K 1 , 4 + P 1 ) -free graphs; (2) for s ≥ 1 , there are finitely many 5-vertex-critical ( P 5 , K 1 , s + P 1 ) -free graphs; (3) for k ≥ 1 , there are finitely many k -vertex-critical ( P 5 , K 3 + 2 P 1 ‾ ) -free graphs. Moreover, we characterize all 5-vertex-critical ( P 5 , H ) -free graphs where H ∈ { K 1 , 3 + P 1 , K 1 , 4 + P 1 , K 3 + 2 P 1 ‾ } using an exhaustive graph generation algorithm.

For graphs G and H, an H-coloring of G is an edge-preserving mapping from V(G) to V(H). Note that if H is the triangle, then H-colorings are equivalent to 3-colorings. In this paper we are interested in the case that H is the five-vertex cycle C₅. A minimal obstruction to C₅-coloring is a graph that does not have a C₅-coloring, but every proper induced subgraph thereof has a C₅-coloring. In this paper we are interested in minimal obstructions to C₅-coloring in F-free graphs, i.e., graphs that exclude some fixed graph F as an induced subgraph. Let P_t denote the path on t vertices, and let S_{a,b,c} denote the graph obtained from paths P_{a+1},P_{b+1},P_{c+1} by identifying one of their endvertices. We show that there is only a finite number of minimal obstructions to C₅-coloring among F-free graphs, where F ∈ {P₈, S_{2,2,1}, S_{3,1,1}} and explicitly determine all such obstructions. This extends the results of Kamiński and Pstrucha [Discr. Appl. Math. 261, 2019] who proved that there is only a finite number of P₇-free minimal obstructions to C₅-coloring, and of Dębski et al. [ISAAC 2022 Proc.] who showed that the triangle is the unique S_{2,1,1}-free minimal obstruction to C₅-coloring. We complement our results with a construction of an infinite family of minimal obstructions to C₅-coloring, which are simultaneously P_{13}-free and S_{2,2,2}-free. We also discuss infinite families of F-free minimal obstructions to H-coloring for other graphs H.