Exponential families of minimally non-coordinated graphs

FRANCISCO J. SOULIGNAC; GABRIEL SUEIRO

La Plata

Workshop; Second Latin-American Workshop on Cliques in Graphs 2006; 2006

A K-coloring of a graph G is an assignment of colors to the cliques of G such that no two cliques with non-empty intersection receive the same color.  A Helly K-complete of a graph G is a collection of pairwise intersecting cliques of G with common intersection. The K-chromatic number and Helly K-clique number of G, denoted by F(G) and M(G), are the sizes of a minimum K coloring and a maximum Helly K-clique of G, respectively. A graph G is coordinated if M(H) = F(H) for every induced subgraph H of G. Recently, partially characterizations of coordinated graphs by minimally forbidden subgraphs were found. In these characterizations, the family of minimally forbidden subgraphs with n vertices has O(1) size, for every n.We show, for every n, a family of minimally non-coordinated graphs of size where every graph of the family has Helly K-clique number 3, O(n) vertices and O(n) edges. Moreover, all graphs of these families have the same number of vertices and edges.For generating these families, we define exchanger and preserver graphs.  We show that by joining one minimal exchanger with one minimal preserver in a specified manner one can obtain a minimally non-coordinated graph. In this work, we describe operations to generate minimal exchangers and preservers.Based on these results, it seems difficult to find a general characterization of coordinated graphs by minimal forbidden induced subgraphs even when restricted to the class of graph with M = 3. This is also a complementary result to the one which states that the problem of determining whether a graph is coordinated is NP-complete for graphs with M = 3.