On A Dual of a Theorem Due to Chvátal-Komlós

By : Sriraman Sridharan

Page No: 245-251

Abstract
Consider a directed graph G and r integers p1, p2, . . . , pr such that p1 + p2 + · · · + pr < B(G), the minimum number of directed paths partitioning the vertex set of the graph G. Let X1, X2, · · · , Xr be any partition of the vertex set X of G. Then there exists an index i such that the stability number (independence number) of the induced subgraph G[Xi ] satisfies the inequality ?(G[Xi ]) > pi . This can be considered as a dual of the theorem of Chvátal-Komlós (see [3]). A generalization of this result is also considered.

Author :
Sriraman Sridharan : Département de Mathématiques et d’Informatique Université de Perpignan Via Domitia 52 Avenue Paul Alduy 66100 Perpignan France