A Recognition Algorithm for a Class of Partitionable Graphs that Satisfies the Normal Graph Conjecture

Mihai Tălmaciu, Elena Nechita, Gloria-Cerasela Crişan

Abstract

A graph is normal if admits a clique cover and a stable set cover so that every clique may intersect every stable set. The Normal Graph Conjecture says that every { 5 C , 7 C ,C7 }-free graph is normal. In this paper we prove this conjecture for the class of O-graphs and we give a recognition algorithm for O-graphs.

Keywords

Normal graphs, O-graphs, Partitionable graphs, Partite graphs, Triangulated graphs.

View full article