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.

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.

The chromatic index of a graph G, χ'(G), is the least number of colors of some edge coloring of G such that no two adjacent edges have the same color. Given a graph G and an integer k, to decide if χ'(G) ≤ k is NP-complete. A graph is an interval graph if it represents the intersection relation of a set of closed intervals in R. A graph is a split graph if its vertex set can be partitioned into a clique and an independent set. A graph is split-interval if it is simultaneously an interval and a split graph. In this paper we show how to determine the chromatic index of all split-interval graphs. Our proof leads to a polynomial-time algorithm to deciding if χ'(G) ≤ k given an integer k and a split-interval graph G.

Given a graph G, an orientation D of G and a perfect matching M of G, it is possible to define the sign (-1 or +1) of M in D. Given k orientations of a graph G, a signature matrix A has rows corresponding to perfect matchings of G and columns corresponding to each of these k orientations such that each entry aij is the sign of the i-th perfect matching on the j-th orientation. A graph is k-Pfaffian if there is a set of k orientations whose signature matrix A is such that the linear system Ax = 1 has a solution. The Pfaffian number of a graph G is the smallest k such that G is k-Pfaffian. We present in this paper a characterization of the signature matrices of graphs with Pfaffian number 6.