This article is cited in
3 papers
Matroid decompositions of graphs
R. I. Tyshkevich
Abstract:
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.
UDC:
519.1 Received: 21.02.1989