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.

A graph is $H$-free if it has no induced subgraph isomorphic to $H$. We characterize all graphs $H$ for which there are only finitely many minimal non-3-colorable $H$-free graphs. Such a characterization was previously known only in the case when $H$ is connected. This solves a problem posed by Golovach et al. As a second result, we characterize all graphs $H$ for which there are only finitely many $H$-free minimal obstructions for list 3-colorability.

The complexity of coloring graphs without long induced paths is a notorious problem in algorithmic graph theory, an especially intruiging case being that of 3-colorability. So far, not much was known about certification in this context. We prove that there are only finitely many 4-critical P6-free graphs, and give the complete list that consists of 24 graphs. In particular, we obtain a certifying algorithm for 3-coloring P6-free graphs, which solves an open problem posed by Golovach et al. Here, P6 denotes the induced path on six vertices. Our result leads to the following dichotomy theorem: if H is a connected graph, then there are finitely many 4-critical H-free graphs if and only if H is a subgraph of P6. This answers a question of Seymour. The proof of our main result involves two distinct automatic proofs, and an extensive structural analysis by hand.