In 1982, Berge defined the class of α-diperfect digraphs. A digraph D is α-diperfect if every induced subdigraph H of D satisfies the following property: for every maximum stable set S of H there is a path partition P of H in which every P ε P contains exactly one vertex of S. Berge conjectured a characterization of α-diperfect digraphs by forbidding induced orientations of odd cycles. In 2023, de Paula Silva, Nunes da Silva and Lee presented an infinite family of counterexamples for Berge’s Conjecture. These digraphs, namely D→ 2t+1 , are acyclic and have stability number two. In this paper, we prove that an acyclic digraph D with stability number two is α-diperfect if and only if D does not contain a D→ 2t+1 as an induced subdigraph.

Let G be a graph and let r be a fixed vertex of G. Two spanning trees T1 and T2 of G rooted at r are edge-independent if for every vertex v ϵ V(G), the paths from v to r in T1 and from v to r in T2 are edge-disjoint. Itai and Zehavi conjectured that for every k-edge-connected graph and any vertex r ϵ V(G) there are k edge-independent spanning trees rooted at r (Edge-Independent Spanning Trees Conjecture). Itai and Rodeh proved the case k = 2, Schlipf and Schmidt proved the case k = 3, and Hoyer and Thomas proved the case k = 4 of the conjecture. In this paper, we prove the case k = 5.

In 1982, Berge defined the class of χ-diperfect digraphs. A digraph D is χ-diperfect if for every minimum coloring S of D there is a path P containing exactly one vertex of each color class of S and this property holds for every induced subdigraph of D. The ultimate goal in this research area is to obtain a characterization of χ-diperfect digraphs in terms of forbidden induced subdigraphs, but this may be a very difficult problem and not likely to be solved in a near future. Berge showed the first examples of obstructions for χ-diperfect digraphs (i.e. minimal non-χ-diperfect digraphs) by presenting orientations of odd cycles and complements of odd cycles that are not χ-diperfect. In 2022, de Paula Silva, Nunes da Silva and Lee showed characterizations of non-χ-diperfect super-orientations of odd cycles and their complements. Moreover, they showed that these structures are not the only obstructions for χ-diperfect digraphs, by presenting new obstructions with stability number two and three. In this paper, we present new obstructions for χ-diperfect digraphs with arbitrary stability number and arbitrary chromatic number.

Motivated by a multitree approach to the design of reliable communication protocols, Itai and Rodeh gave a linear time algorithm for finding two independent spanning trees in a 2-connected graph. Cheriyan and Maheshwari gave an $O(|V|^2)$ algorithm for finding three independent spanning trees in a 3-connected graph. In this paper we present an $O(|V|^3)$ algorithm for finding four independent spanning trees in a 4-connected graph. We make use of chain decompositions of 4-connected graphs.

In this paper, we describe an O(|V(G)||E(G)|) algorithm for finding a nonseparating planar chain in a 4-connected graph G, which will be used to decompose an arbitrary 4-connected graph into planar chains. This work was motivated by the study of a multitree approach to reliability in distributed networks, as well as the study of nonseparating induced paths in highly connected graphs.

In this paper we give a decomposition of a 4-connected graph G into nonseparating chains, which is similar to an ear decomposition of a 2-connected graph. We also give an $O(|V(G)|^2|E(G)|)$ algorithm that constructs such a decomposition. In applications, the asymptotic performance can often be improved to $O(|V(G)|^3)$.This decomposition will be used to find four independent spanning trees in a 4-connected graph.