Matroid decompositions of graphs

R. I. Tyshkevich

Diskretnaya Matematika, Tome 1 (1989) no. 3, pp. 129-138.

Résumé

A graph $G$ is called M-graph, if it satisfies one of the following conditions: 1) $G$ is a simple graph, every connected component of which is a complete graph; 2) $G$ is obtained from a graph described in 1) or from the empty set as a result of joining the dominating vertices with loops. It has been proved that every graph can be represented in the form of an intersection of $M$-graphs such that each of its sets of independent vertices is independent in some component. The minimal number $m(G)$ of components in such representations is called the matroidal number of the graph $G$. If $G=G_1\cap G_2\cap\dots\cap G_m$ is a representation of that kind and $IG$ is the set for which all independent subsets of vertices of the graph $G$ and the empty set serve as elements then $$ IG=IG_1\cup IG_2\cup\dots\cup IG_m, $$ where $(VG,IG\sb k)$ is a matroid with the system of independent sets $IG_k$. Here $VG$ is the set of vertices of the graph $G$. The parameter $m(G)$ is equal to the minimal number of matroids, into the set-theoretic union of which the independence system $IG$ can be decomposed. The structure of graphs with $m(G)$ bounded by a constant has been described. The value $m(G)$ for splittable graphs has been found.