Equitable partitions into matchings and coverings in mixed graphs (Q2237227): Difference between revisions

A mixed graph \(G = (V, E, A)\) consists of a set of undirected edges \(E\), and a set of directed arcs \(A\), living in the same vertex set \(V\). (In mixed graphs, the authors consider undirected edges to have both directions where necessary.) The authors consider generalisations of the notion of edge covers in graphs in the setting of mixed graphs. The two main notions considered read as follows. \par i) Given a mixed graph \(G = (V,E,A)\), a mixed edge cover \(F \subseteq E \cup A\) is such that for every \(v \in V\) there is a directed path in \(F \cap A\) starting from some endpoint of an edge in \(F \cap E\), and ending in \(v\). \par ii) A mixed covering forest \(F \subseteq E \cup A\) is such that the underlying undirected graph formed by \(F\) is acyclic and every vertex is covered at least once by \(F\) (meaning, is the endpoint of some edge in \(F\), recalling undirected edges are assumed to have both endpoints). The authors mainly consider problems of partitioning the edge-arc set of mixed graphs into ``almost-equitable'' mixed edge covers or mixed covering forests, for various notions of what it means to be almost-equitable. For instance, one of their results is the following. If \(G = (V,E,A)\) is a mixed graph that can be partitioned into \(k\) mixed matching forests, then \(G\) can be partitioned into \(k\) matching forests \(F_1, \dotsc, F_k\) in such a way that for every \(1 \leq i\), \(j \leq k\), we have \(||F_i|-|F_j|| \leq 1\), \(||F_i \cap A|-|F_j \cap A|| \leq 2\), and \(||F_i \cap E| - |F_j \cap E|| \leq 2\). En route to these partitioning results, the authors also prove various combinatorial, algorithmic and polyhedral results concerning mixed matching forests and mixed edge covers.