93-17 On the Structure of Co-Critical Graphs

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