Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

The perfection and recognition of bull-reducible Berge graphs

Hazel Everett;  Celina M. H. de Figueiredo;  Sulamita Klein;  Bruce Reed — 2005

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 x , a , b , c , d and five edges x a , x b , a b , a d , b c . 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...

Finding H -partitions efficiently

Simone Dantas;  Celina M. H. de Figueiredo;  Sylvain Gravier;  Sulamita Klein — 2005

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We study the concept of an H -partition of the vertex set of a graph G , 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 H , 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, 4 -part,...

Page 1

Download Results (CSV)