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

**Mihai TĂLMACIU**, **Elena NECHITA**, **Gloria-Cerasela CRIŞAN**

University of Bacău, Department of Mathematics and Informatics

8 Spiru Haret, Bacău, ROMANIA

**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 {,,}-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.

**Mihai Tălmaciu** received his M.S. degree in Informatics from *Alexandru Ioan Cuza* University, Iaşi, Romania, in 1976 and the his Ph.D. degree in Information Sciences from the same institution in 2002. He is a Professor of the Mathematics and Informatics Department of the *University of Bacău*, Bacău, Romania. His areas of research include Combinatorics and Graphs Theory, Graph Algorithms and Numerical Analysis.

**Elena Nechita** received her M.S. degree in Informatics from *Alexandru Ioan Cuza University*, Iaşi, Romania, in 1987 and her Ph.D. degree in Information Sciences from the same institution in 2000. She is an Associate Professor of the Mathematics and Informatics Department of the *University of Bacău*, Bacău, Romania. Her areas of research include: Probability Theory, Artificial Intelligence and Evolutionary Computing.

**Gloria-Cerasela Crişan **received her M.S. degree in Informatics from *University of Bucharest*, Romania, in 1986 and the Ph.D. degree in Information Sciences from *Alexandru Ioan Cuza University*, Iaşi, in 2008. She is a Lecturer of the Mathematics and Informatics Department of the *University of Bacău*, Bacău, Romania. Her areas of research include Artificial Intelligence and Evolutionary Computing.

**>>Full text **

**CITE THIS PAPER AS**:

Mihai TĂLMACIU, Elena NECHITA, Gloria-Cerasela CRIŞAN, **A Recognition Algorithm for a Class of Partitionable Graphs that Satisfies the Normal Graph Conjecture**, *Studies in Informatics and Control*, ISSN 1220-1766, vol. 18 (4), pp. 349-354, 2009.

**1. Introduction**

Normal graphs form a superclass of perfect graphs and can be considered as closure of perfect graphs by means of co-normal products [9] and graph entropy [8]. Perfect graphs have been characterized as those without odd holes and antiholes as induced subgraphs (Strong Perfect Graph Theorem, [5]). Korner and de Simone [6] observed that C* _{5}*,C

*, are minimal, not normal graphs. As a generalization of the Strong Perfect Graph Theorem, Korner and de Simone conjectured that every {C*

_{7}*,C*

_{5}*,}-free graph is normal (Normal Graph Conjecture, [11]). Wagler [15] proved the conjecture for the class of circulant graphs.*

_{7}The entropy [10] of a graph is a functional depending both one the graph itself and on a probability distribution on its vertex set.

In [4] we find a recent survey of results on combinatorial optimization problems in which the objective function is the entropy of a discrete distribution.

In [8], the authors prove that a graphs is perfect if and only if it “splits graph entropy”. Using this derive the following strengthening of the normality of perfect graphs:

*Let G be a perfect graph. Then G contains a family A of independent sets and a family B of cliques with the following properties: *

*i) |A|+|B|=k+1; *

*ii) the sets in A (B) cover all vertices; *

*iii) the incidence vectors of sets in A (B) are linearly independent; *

*iv) every AÎ A intersects every BÎ B.*

The class of perfect graphs is important because many problems of interest in practice but intractable in general can be solved efficiently when restricted to the class of perfect graphs [6].

Partitionable graphs contain all the potential counterexemples to Berge’s famous Strong Perfect Graph Conjecture ([3]) which was proved by Chudnovski, Robertson, Seymour, and Thomas in [5]. Partitionable graphs ([7]) are one of the central objects in the theory of perfect graphs due to the following theorem of Lovasz: *A graph is perfect if and only if* a (H)w (H)³ n(H) *for every induced subgraph* H *of* G.

In this paper we find a class of partitionable graphs that are not perfect, but are normal. We prove Normal Graph Conjecture for the class of O-graphs and give a recognition algorithm for O-graphs.

Throughout this paper, *G*=(*V*,*E*) is a simple (i.e. finite, undirected, without loops and multiple edges) graph [2]. Let denote the complement graph of *G*. For *UÍ V* let *G*(*U*) denote the subgraph of *G* induced by *U*. By *G*–*X* we mean the graph *G*(*V*–*X*), whenever *XÍ V*, but we often denote it simply by *G*–*v *(“ n Î *V*), when there is no ambiguity. If *vV* is a vertex in *G*, the neighborhood N* _{G}*(n) denotes the vertices of

*G*–

*v*that are adjacent to

*v*. We write

*N*(

*v*) when the graph

*G*appears clearly from the context. The neighborhood of the vertex

*v*in the complement of the graph

*G*is denoted by (n). For any subset

*S*of vertices in

*G,*the neighborhood of

*S*is

*N(S)*=È n Î

*–*

_{S}N(n)*S*and

*N*[

*S*]=

*SÈ N*(

*S*). A clique is a subset of

*V*with the property that all the vertices are pairwise adjacent. The

*clique*

*number*(

*density*) of

*G*, denoted by w (

*G*) is the cardinal of the maximum clique. A clique cover is a partition of the vertices set such that each part is a clique. q (

*G*) is the cardinal of a smallest possible clique cover of

*G*; it is called the

*clique*

*cover*

*number*of

*G*. The

*stability*

*number*of

*G*is a (

*G*)=; the

*chromatic*

*number*of

*G*is c (

*G*)=.

By P_{n}, C_{n}, K_{n} we mean a chordless path on *n³ *3 vertices, the chordless cycle on *n³ *3 vertices, and the complete graph on *n³ *1 vertices. If *e*=*xyÎ E*, we also write *x~y*; we also write *x*≁*y* whenever *x*, *y* are not adjacent in *G*. A set *A* is totally adjacent (non adjacent) with a set *B* of vertices (*AÇ B*=f) if *ab* is (is not) edge, for any *a* vertex in *A* and any *b* vertex in *B*; we note with *A~B* (*A≁B*). A graph *G* is *F*-free if none of its induced subgraphs is in *F*.

A graph *G* is called a –*partitionable* if

a (*G*)=q (*G*) holds.

A graph *G* is *perfect* if a (*H*)=q (*H*) (or, equivalent, c (*H*)=w (*H*)) holds for every induced subgraph *H* of *G*, i.e. every induced subgraph is a-partitionable.

We call *matching* a set *FÌ E* such that the edges in *F* are not adjacent.

A [*p*,*q*,*r*]-*partite* graph is a graph whose set of vertices is partitioned in *p* stable sets *S _{1},S_{2},…,S_{p}*, each of them consisting of exactly

*q*vertices and every subgraph induced by

*S*consists of exactly

_{iÈ }S_{j}*r*independent edges, for 1£

*i<j£ p*.

A *circulant C*^{k,n} is a graph with nodes 1,…,*n* where *ij* is an edge if *i* and *j* differ by at most *k*(*mod n*) and *i¹ j*.

The subset *AÌ V* is called a *cutset* if *G*–*A* is not connected. If, in addition, some *vÎ A* is adjacent to every vertex in *A*-{*v*}, then *A* is called a star cutset and *v* is called the center of *A*.

The paper is organized as follows. In Section 2 we give sufficient conditions for a graph to be normal. In Section 3 we give a recognition algorithm for O-graphs.

**4. Conclusions and Future Work**

In this paper we have proved that the normal graph conjecture is true for O-graphs and we have presented a recognition algorithm for these graphs.

Our future work will verify the conjecture on classes of graphs characterized by means of forbidden subgraphs.

**References**:

- Balas, E., C. S. Yu
**, Finding a Maximum Clique in an Arbitrary Graph**. SIAM Journal of Computing 15, 1986, pp. 1054-1068. - Berge, C.
**, Graphs**, North-Holland, Amsterdam. 1985. - Boros, E., V. Gurvich, S. Hougardy
**, Recursive Generation of Partitionable Graphs**, http://www2. informatik.hu-berlin.d/~hougardy/paper /BGH-JGT.pdf, 2002. - Cardinal, J., S. Fiorini, G. Jeret
**, Minimum Entropy Combinatorial Optimization Problems**, Lecture Notes in Computer Science, 2009, pp. 79-88. - Chudnovski, M., N. Robertson, P. D. Seymour, R. Thomas
**, Strong Perfect Graphs Theory**, Annals of Mathematics 164, 2006, pp. 51-229. - Chudnovski, M., N. Robertson, P. D. Seymour, R. Thomas
**, Progress on Perfect Graphs**, Mathematical Programming Ser. B 97, 2003, pp. 405-422. - Conforti, M., G. Cornuejols, G. Gasparyan, K. Vuskovic
**, Perfect Graphs, Partitionable Graphs and Cutset**, Combinatorica 22(1), 2002, pp. 19-33. - Csiszar, I., J. Korner, L. Lovasz, K. Marton, G. Simonyi
**, Entropy Splitting for Antiblocking Corners and Perfect Graphs**, Combinatorica 10, 1990, pp. 27-40. - Korner, J.
**, An Extension of the Class of Perfect Graphs**, Studia Scientiarum Mathematicarum Hungarica 8, 1973, pp. 405-409. - Korner, J. K. Marton
**, Graphs that Split Entropies**, SIAM J. Discrete Math. Volume 1, 1988, pp. 77-79. - Korner, J., C. de Simone
**, On the Odd Cycles of Normal Graphs**, Discrete Applied Mathematics 94, 1999, pp. 161-169. - Olaru, E., M. Talmaciu
**, A Class of Partitionable Graphs**, Bull. Math. Soc. Sc. Math. Roumanie, Tome 48(96), No. 3, 2005, pp. 313-317. - Talmaciu, M.
**, Decomposition Problems in the Graph Theory with Applications in Combinatorial Optimization**– Ph. D. Thesis, University “Al. I. Cuza” Iasi, Romania, 2002. - Talmaciu, M., E. Nechita
**, Recognition Algorithm for Diamond-free Graphs**, INFORMATICA, Vol. 18, No. 3, 2007, pp. 457-462. - Wagler A. K.
**, The Normal Graph Conjecture is True for Circulant Graphs**. Tehnical Raport ZR, 2004, pp. 04-06, ZIB. - Warren, J. S., I. V. Hicks, (2006)
**Combinatorial Branch-and-Bound for the Maximum Weight Independent Set Problem**, http://ie.tamu.edu/People/ faculty/Hicks/jeff.rev.pdf, working paper, accesed July 10, 2009.