$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Zakładu Matematyki Dyskretnej
Wydziału Matematyki Stosowanej
AGH

Wyjątkowo w piątek

28 września 2001 roku,

Wyjątkowo wcześnie, bo o godzinie 10:15

w sali 304, łącznik A-3-A-4, A G H

Henri THUILLIER

(LIFO, Orleans (Francja)

wygłosi referat pod tytułem:

On Cayley partitionable graphs.

Arnaud Pêcher, H. Thuillier

A graph $G$ is perfect if for every induced subgraph H of G, its chromatic number $\chi(H)$ is equal to its clique number $\omega(H)$. C. Berge conjectured in 1961 that perfect graphs are exactly the graphs with no induced odd cycle and no complement of an induced odd cycle, or equivalently that minimal imperfect graphs are odd induced cycles and their complements. This well-known open conjecture is called the Strong Perfect Graph Conjecture. Following Bland, Huang and Trotter [2] a graph $G$ is said to be partitionable if there exist two integers $\alpha$ and $\omega$ such that $G$ has $\alpha \ \omega +1$ vertices and for every vertex $v$ of $G$, the induced subgraph $G \setminus {v}$ has a partition in $\alpha$ $\omega$-cliques and a partition in $\omega$ $\alpha$-stables. Padberg proved in 1974 that every minimal imperfect graph is partitionable.

In 1979, Chvátal, Graham, Perold and Whitesides introduced two constructions for making partitionable graphs [4]. New results focused on a generalization of the second construction (the $CGPW$-graphs) have been recently obtained by Arnaud Pêcher [5]. The aim of the talk is the presentation of some of his results [5]. A normalized graph is a graph such that for every edge $e = \{x,y\}$, there exists a maximum clique containing both $x$ and $y$. It was noticed that every $CGPW$-graph is a normalized Cayley partitionable graph of a cyclic group [1]. The notion of Cayley partitionable graphs of a finite group (not necessarily cyclic)is closely related with the group theoretic notion of near-factorization [3]. Two subsets A and B of a finite group $\Gamma$ of order $n > 1$ and operator $*$ are said to form a near-factorization of $\Gamma$ if and only if $n = \vert A\vert.\vert B\vert+1$ and there is an element $u(A,B)$ of $\Gamma$ such that $A*B = \Gamma \setminus u(A,B)$. If $(A, B)$ is a near-factorization of a finite group $\Gamma$ then the Cayley graph $G = \Gamma (A, B)$ with connection set $(A^{-1}*A) \setminus {e}$ is a normalized partitionable graph and, conversely, if $G$ is any Cayley partitionable graph on a group $\Gamma$, then there exists a near-factorization $(A, B)$ of $\Gamma$ such that $\Gamma (A, B)$ is the normalized graph of $G$. This equivalence motivated this research: how to produce near-factorizations of some finite groups, so as giving rise to 'new' partitionable graphs. At first sight, things seem to go pretty well: beyond the class of the cyclic groups, all the dihedral groups have near-factorizations [3]. A basic result explaining the relationship between near-factorizations of the cyclic groups and near-factorizations of the dihedral groups, for half of the dihedral groups, is given. In fact it is explored why so few groups have near-factorizations, and new Cayley partitionable graphs which do not belong to any of the known constructions will be given.

Succinct bibliography :

[1] G. Bacsó, E. Boros, V. Gurvich, F. Maffray, and M. Preismann, On minimally imperfect graphs with circular symmetry, J. Graph Theory 29 (1998), 209-225.

[2] R.G. Bland, H.C. Huang, and L.E. Trotter, Graphical properties related to minimal imperfection, Disc. Math. 27 (1979), 11-22.

[3] D. De Caen, D.A. Gregory, I.G. Hughes, and D.L. Kreher, Near-factors of finite groups, Ars Combinatoria 29 (1990), 53-63.

[4] V. Chvátal, R.L. Graham, A.F. Perold, and S.H. Whitesides, Combinatorial designs related to the perfect graph conjecture, Annals Discrete Math. 21 (1984), 197-206.

[5] A. Pêcher, Graphes de Cayley partitionnables, PHD Thesis, L.I.F.O., Université d'Orléans (France), December 2000.

Serdecznie zapraszamy wszystkich chętnych !