The recently announced Strong Perfect Graph Theorem states that the class of
perfect graphs coincides with the class of graphs containing no induced
odd cycle of length at least 5 or the complement of such a cycle. A
graph in this second class is called Berge. A bull is a graph with five
vertices and five edges . A graph is
bull-reducible if no vertex is in two bulls. In this paper we give a
simple proof that every bull-reducible Berge graph is perfect. Although
this result follows directly from...
We study the concept of an -partition of the vertex set of a
graph , which includes all vertex partitioning problems into
four parts which we require to be nonempty with only external
constraints according to the structure of a model graph , with
the exception of two cases, one that has already been classified
as polynomial, and the other one remains unclassified. In the
context of more general vertex-partition problems, the problems
addressed in this paper have these properties: non-list, -part,
external...
The recently announced Strong Perfect Graph Theorem states that the class of perfect graphs coincides with the class of graphs containing no induced odd cycle of length at least 5 or the complement of such a cycle. A graph in this second class is called Berge. A bull is a graph with five vertices and five edges . A graph is bull-reducible if no vertex is in two bulls. In this paper we give a simple proof that every bull-reducible Berge graph is perfect. Although this result follows directly from...
We study the concept of an -partition of the vertex set of a graph , which includes all vertex partitioning problems into four parts which we require to be nonempty with only external constraints according to the structure of a model graph , with the exception of two cases, one that has already been classified as polynomial, and the other one remains unclassified. In the context of more general vertex-partition problems, the problems addressed in this paper have these properties: non-list, -part,...
Download Results (CSV)