$\parbox{7cm}{ {\Huge\bf SEMINARIUM}}$
Matematyka Dyskretna
(prowadzone przez M.Woźniaka)

We wtorek, 22 marca 2005 roku, o godzinie 12:45

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

Peter MIHÓK i Jozef BUCKO

(Faculty of Economics, Technical University, Koszyce)

wygłoszą referat pod tytułem:

Vertex Ramsey Minimal Graphs

and Minimal Forbidden Subgraphs

Let ${\cal P},$ be a property of graphs. A graph $G$ is vertex $({{\cal P}},k)$-colourable if the vertex set $V(G)$ of $G$ can be partitioned into $k$ sets $V_1, V_2,\dots, V_k$ such that the subgraph $G[V_i]$ of $G$ belongs to ${\cal P}$, $i=1,2,\dots,k$. If ${\cal P}$ is a hereditary property, then the set of minimal forbidden subgraphs of ${\cal P}$ is defined as follows: ${\mbox{\boldmath $F$}}({\cal P}) = \bigl \{ G: G\notin {\cal P}\mbox{ but each proper subgraph } H \mbox { of } G \in {\cal P}\bigr \}.$

We write $G\stackrel{v}{\longrightarrow}(H)^{k}$, $k\geq 2$, if for each $k$-colouring $V_1, V_2,\dots, V_k$ of a graph $G$ there exists $i$, $1\leq i\leq k$, such that the graph induced by the set $V_i$ contains $H$ as a subgraph. A graph $G$ is called $(H)^{k}{\--}$ vertex Ramsey minimal if $G\stackrel{v}{\longrightarrow}(H)^{k}$, but $G'\stackrel{v}{\not\rightarrow}(H)^{k}$ for any proper subgraph $G'$ of $G$.

Every additive hereditary property ${\cal P}$ is uniquely determined by the set of connected minimal forbidden subgraphs. Note that ${\mbox{\boldmath $F$}}({\cal P})$ may be finite or infinite.

For the class ${\cal O}^k$ of all $k$-colorable graphs the set $F$ $({\cal O}^k)$ consists of all $(k+1)$- edge critical graphs. A long standing open problem whether the family ${\mbox{\boldmath $F$}}({\cal P}^k)$ may be finite for $k\geq 2$ was solved by A. Berger. She proved that ${\mbox{\boldmath $F$}}({\cal P}^k)$ is infinite whenever $k\geq 2$. For a property ${\cal P}$ with ${\mbox{\boldmath $F$}}({\cal P})= \{H\}$, ${\mbox{\boldmath $F$}}({\cal P}^k)$ is identical with the set of all $(H)^{k}$-vertex Ramsey minimal graphs. This sheds some new light on the old Ramsey questions. In the language of the Vertex Ramsey Theory Berger's result asserts that the family of vertex Ramsey minimal graphs for multiple colours (at least two colours) is infinite for each connected, fixed $H$.

In our talk we will present several results concerning the structure of minimal forbidden subgraphs, which implies some results on vertex Ramsey minimal graphs, as well.

Serdecznie zapraszamy wszystkich chętnych !