## DIMACS TR: 93-17

## On the Structure of Co-Critical Graphs

### Authors: Anna Galluccio, Miklos Simonovits, Gabor Simonyi

**
ABSTRACT
**

Given a family $L_1,\dots,L_r$ of graphs, a graph $G$ is called
$(L_1,\dots,L_r)$--co-critical if one can colour its edges in $r$
colours so that the subgraph defined by the $\nu\th$ colour contains
no $L_{\nu}$, however, $G$ is saturated for this property: adding any
edge to $G$ we get a $G^*$ with the property that arbitrarily
colouring $G^*$ in $r$ colours for some $\nu$ we shall have a
monochromatic copy of $L_{\nu}$ in the $\nu\th$ colour. (The notion
comes from J. Nesetril.) In this paper we shall investigate the
structural properties of $(K_3,K_3)$-co-critical graphs, present
various constructions of such graphs and establish some of their
properties.

Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-17.ps

DIMACS Home Page