×

Ball structures and colorings of graphs and groups. (English) Zbl 1147.05033

Mathematical Studies Monograph Series 11. Lviv: VNTL Publishers (ISBN 966-7148-99-8/pbk). 147 p. (2003).
Let \(X\) be a set and \(\mathcal{F}\) be a family of subsets of \(X.\) A coloring \(\chi :X\rightarrow \kappa \) of \(X\) (a surjective map of \(X\) onto a cardinal \(\kappa \)) is \(\mathcal{F}\)-surjective (-injective, -nonconstant, -bijective) if the restriction \(X| _{\mathcal{F}}\) is surjective (injective, nonconstant, bijective) for all \(F\) in \(\mathcal{F}.\) Set
\[ \begin{aligned} \mu _{\text{sur}}( \mathcal{F}) &= \sup \{\kappa ;\text{ there is an }\mathcal{F}\text{-surjective coloring } \chi :X\rightarrow \kappa \},\\ \mu _{\text{inj}}(\mathcal{F)} &= \min \{\kappa ;\text{ there is an }\mathcal{F}\text{-injective coloring }\chi :X\rightarrow \kappa \},\text{and} \mu _{\text{non}}(\mathcal{F)} &= \min \{\kappa ;\text{ there is an }\mathcal{F}\text{-nonconstant coloring }\chi :X\rightarrow \kappa \}.\end{aligned} \]
The authors state that the above coloring invariants provide a unifying point of view for several areas, e.g., Ramsey type results, irresolvable topological spaces, graph theory. A couple of examples: the van der Waerden theorem is equivalent to \(\mu _{\text{non}}(\mathcal{F)=\aleph }_{0},\) where \(\mathcal{F}\) is the family of all arithmetic progressions in \( \mathbb{N} \) of given length, while for the chromatic number \(\chi (G)\) of a graph \(G\) we have \(\chi (G)=\) \(\mu _{\text{non}}(\mathcal{F)=\mu }_{inj}(\mathcal{F)}\), where \(\mathcal{F}\) is the set of edges of \(G.\)
In this book the studied families \(\mathcal{F}\) come from graph theory or from the theory of groups. In both cases a special attention is paid to the ball structure, the concept introduced by the first author. The \(r\)-ball is a direct extension of the notion of the sphere of radius \(r\) in a metric space.
The book comprises 13 sections. The first six of them are devoted to graphs (Balanced partitions of finite graphs, Balanced partitions of infinite graphs, Quasicycles and quasirays, Quasihamiltonian graphs, Chromatic numbers of graphs, Kaleidoscopical graphs), the sections 7 and 8 deal with semigroups and groups (Coloring of \(G\) spaces, Kaleidoscopical subsets in groups), the next three sections are on ball structures (Ball structures, Morphism of ball structures, Size of subsets in ball structures), while the last two sections deal with the order of a subgroup of a group (Size of subsets in graphs or groups, On size of generating subsets in groups).
Except for Section 7 and Section 8, a vast majority of results of the book were published previously [see K. D. Protasova, “Balanced graph partitions”, Math. Notes 79, No. 1, 116–121 (2006); translation from Mat. Zametki 79, No. 1, 127–133 (2006; Zbl 1133.05077); K. D. Protasova, Dopov. Nats. Akad. Nauk Ukr., Mat. Pryr. Tekh. Nauky 2003, No. 6, 21–25 (2003; Zbl 1033.05086); I. V. Protasov, “Combinatorial size of subsets of groups and graphs”, Ukrainian mathematical congress – 2001. Algebraic structures and their applications. Proceedings of the third international algebraic conference held in framework of the Ukrainian mathematical congress, Kiev, Ukraine, July 2–8, 2001. Kyïv: Instytut Matematyky NAN Ukraïny. 339–345 (2002; Zbl 1099.05506); V. A. Evstigneev, Application of graph theory to computer programming (Russian), Nauka, Moscow (1985; Zbl 0561.90060); I. V. Protasov, “Morphisms of ball’s structures of groups and graphs”, Ukr. Math. J. 54, No. 6, 1027–1037 (2002) and Ukr. Mat. Zh. 54, No. 6, 847–855 (2002; Zbl 1003.05053); A. Gnatenko and I. Protasov, “Combinatorial size of subsets of semigroups and or-graphs”, Visn. L’viv. Univ., Ser. Mekh.-Mat. 61, 92–97 (2003; Zbl 1037.20059); I. V. Protasov, “Small systems of generators of groups”, Math. Notes 76, No. 3, 389–394 (2004); translation from Mat. Zametki 76, No. 3, 420–426 (2004; Zbl 1078.20032)].
While most of the book is written as a monograph, some parts will remind the reader of a textbook. For example, Section 5 contains a proof of the Brooks theorem and of the theorem that a graph \(G\) is bipartite iff each cycle of \(G\) is of even length. It is followed by an example, even with a hint, that, for a graph of order \(n,\) \(\chi (G)=n\) if and only if \(G\) is a complete graph. This leaves the reader wondering whom the authors had in mind when writing the book.

MSC:

05C15 Coloring of graphs and hypergraphs
05-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to combinatorics
05-02 Research exposition (monographs, survey articles) pertaining to combinatorics