HEREDITARY PROPERTIES OF GRAPHS

PETER MIHÓK, GABRIEL SEMANIŠIN, JOZEF BUCKO

Košice, Slovakia

Abstract:

"Graph coloring deals with the fundamental problem of partitioning a set of objects into classes, according to certain rules... Problems, results and definitions in graph coloring theory have variations, extensions and/or reformulations ad infinitum..." Bjarne Toft and Tommy R. Jensen, Graph Coloring Problems, Wiley-Interscience 1995

A convenient language that may be used in formulating problems of graph colouring in a general setting is the language of reducible and decomposable properties of graphs. Let us denote by ${\cal I}$ the class of all finite simple graphs. A property of graphs ${\cal P}$ is any nonempty proper isomorphism closed subclass of ${\cal I}$. Let ${\cal P}_1,{\cal P}_2, \dots,{\cal P}_n$ be properties of graphs. A graph $G$ is vertex $({\cal P}_1,{\cal P}_2, \dots,{\cal P}_n)$-colorable($G$ has property ${\cal P}_1{\scriptstyle \circ}{\cal P}_2{\scriptstyle \circ}\cdots{\scriptstyle \circ}{\cal P}_n$) if the vertex set $V(G)$ of $G$ can be partitioned into $n$ sets $V_1, V_2,\dots, V_n$ such that the subgraph $G[V_i]$ of $G$ induced by $V_i$ belongs to ${\cal P}_i$; $i=1,2,\dots,n$. In the case ${\cal P}_1 = {\cal P}_2 = \dots = {\cal P}_n = {\cal P}$ we write ${\cal P}_1 {\scriptstyle \circ}{\cal P}_2 {\scriptstyle \circ}\dots {\scriptstyle \circ}{\cal P}_n = {\cal P}^n$ and we say that $G \in {\cal P}^n$ is $({\cal P},n)$-colorable (partitionable). Let us denote by ${\cal O}$ the class of all edgeless graphs. The classical graph coloring problems deals with so-called proper coloring where ${\cal P}_1 = {\cal P}_2 = \dots = {\cal P}_n = {\cal O}$ so that a graph $G$ is $k$-colorable if and only if $G\in{\cal O}^k$. The basic property of the proper coloring is that every induced subgraph of a $k$-colorable graph is $k$-colorable and if every connected component of a graph $G$ is $k$-colorable, then $G$ is $k$-colorable, too. We consider as the generalizations of the proper coloring only such vertex $({\cal P}_1,{\cal P}_2, \dots,{\cal P}_n)$-colorings where the properties $({\cal P}_1,{\cal P}_2, \dots,{\cal P}_n)$ preserve the above mentioned requirements i.e. they are closed to induced subgraphs and disjoint union of graphs. Such properties of graphs are called induced-hereditary and additive. The set of all additive induced-hereditary properties will be denoted by $\mbox{\sf\makebox[0ex][l]{\rule[0ex]{.15ex}{1.55ex}}\makebox[0ex][l]{\rule[1.54ex]{.4ex}{.05ex}}\makebox[.05ex][l]{\rule[0ex]{.4ex}{.05ex}}M}^a$.

Let ${\cal P}_1,{\cal P}_2,\dots,{\cal P}_n \in \mbox{\sf\makebox[0ex][l]{\rule[0ex]... ...][l]{\rule[1.54ex]{.4ex}{.05ex}}\makebox[.05ex][l]{\rule[0ex]{.4ex}{.05ex}}M}^a$, an edge $({\cal P}_1,{\cal P}_2, \dots,{\cal P}_n)$-decomposition of a graph $G$ is the decomposition $E_1,E_2,\dots, E_n$ of its edge set $E(G)$ satisfying that for each $i=\{1,2,\dots,n\}$ the induced subgraph $G[E_i]$ has property ${\cal P}_i$. A property ${\cal Q}={\cal P}_1\oplus{\cal P}_2 \oplus\cdots\oplus{\cal P}_n$ is defined as the set of all graphs having a $({\cal P}_1,{\cal P}_2, \dots,{\cal P}_n)$-decomposition. If ${\cal P}_1={\cal P}_2=\cdots {\cal P}_n={\cal P}$ we simply write $n \times {\cal P}$ instead of ${\cal P}\oplus{\cal P}\oplus\cdots\oplus{\cal P}$. Note that the property ${\cal O}$ is the neutral element for the operation $\oplus$. More precisely, if ${\cal P}$ is an induced-hereditary property then ${\cal P}\oplus{\cal O}={\cal P}$. Let ${\cal P}_1,{\cal P}_2, \dots,{\cal P}_n$ be additive induced-hereditary, then the properties ${\cal R} ={\cal P}_1{\scriptstyle \circ}{\cal P}_2{\scriptstyle \circ}\cdots{\scriptstyle \circ}{\cal P}_n$ and ${\cal Q}={\cal P}_1\oplus{\cal P}_2 \oplus\cdots\oplus{\cal P}_n$ are also additive induced-hereditary. Reducible and decomposable properties of graphs express a natural generalization of vertex and edge $k$-colorable graphs. The detailed notation, basic results and many examples of induced-hereditary properties may be found in [1] and [2] (see also [3]). The basic results on the cardinality of induced hereditary properties are presented in [4].

An additive induced-hereditary property ${\cal R} ({\cal Q})$ is said to be reducible (decomposable) if there exist additive induced-hereditary properties ${\cal P}_1$ and ${\cal P}_2$ such that ${\cal R} ={\cal P}_1{\scriptstyle \circ}{\cal P}_2 ({\cal Q}={\cal P}_1\oplus{\cal P}_2)$; otherwise the property ${\cal R}$ is irreducible (indecomposable). The notion of reducible property have been introduced in connection with generalized graph colouring and the existence of uniquely partitionable graphs in [5,6]. In our three talks we will present a survey of recent results and open problems on reducible and decomposable properties of graphs. Necessary and sufficient conditions for a property to be irreducible will be given. The proof of the Unique Factorization Theorem for additive induced-hereditary properties will be presented.