# zbMATH — the first resource for mathematics

Color-induced graph colorings. (English) Zbl 1365.05006
SpringerBriefs in Mathematics. Cham: Springer (ISBN 978-3-319-20393-5/pbk; 978-3-319-20394-2/ebook). xiv, 118 p. (2015).
The book gives a detailed survey on concepts of vertex-colorings which are induced by edge-colorings. For each coloring introduced, background and motivation are provided, followed by an overview of the state of the art in this topic.
The book is divided into eight chapters. After a short introduction, Chapters 2–5 deal with the concept of irregularity. A graph $$G$$ is irregular, if its vertices have pairwise different degree in $$G$$. It is known that no simple irregular graph exists. The situation changes for connected multigraphs with at least three vertices. More general, for a weight function $$c$$ on $$E(G)$$ – also considered as an edge-coloring in this book – define a function $$c'$$ on the vertex set of $$G$$ with $$c^\prime(v) = \sum_{e \in E(v)}c(e)$$, where $$E(v)$$ is the set of edges incident to $$v$$. A weighted graph $$(G,c)$$ is irregular if $$c^\prime(v) \not= c'(w)$$ for any two vertices $$v, w$$ of $$G$$, where $$c^\prime$$ is considered as a vertex-coloring which is induced by $$c$$.
Chapters 2–5 study chromatic parameters which are related to the irregularity of $$c^\prime$$, and where $$c$$ is not necessarily a proper edge-coloring. In Chapter 2, $$c$$ maps to the natural numbers, while $$c$$ maps to the sets of integers modulo $$k$$ ($$k \geq 2$$) in Chapter 3. Chapter 4 modifies these approaches by defining $$c^\prime(v)$$ to be set $$\{c(e) : e \in E(v) \}$$. Chapter 5 extends this approach to multisets. Here, $$c^\prime(v)$$ is as an ordered $$k$$-tuple $$(a_1, \dots,a_k)$$, where $$a_i$$ is the number of edges of $$E(v)$$ which are colored with color $$i$$.
In Chapters 6 and 7 the condition on $$c^\prime$$ is relaxed to being a proper vertex-coloring. This leads to the study of the proper sum neighbor-distinguishing chromatic index (or for short the sum distinguishing index). It follows a short introduction to the 1-2-3 conjecture and to the multiset distinguishing index in Chapter 6. Chapter 7 changes then to colorings with colors from the integers modulo $$k$$ ($$k \geq 2$$).
Chapters 8 and 9 study similar concepts where $$c$$ is required to be a proper edge-coloring.
The book deals with very recent concepts in graph coloring. Keywords are irregular colorings, strong colorings, modular colorings, edge-graceful colorings, twin edge colorings and binomial colorings. It contains a rich set of results. Lower and upper bounds are proved for the coloring parameters and they are determined for some specific classes of graphs. It is well written and provides a good introduction and survey on color-induced graph colorings for researchers and graduate students in the mathematics community, especially the graph theory community.

##### MSC:
 05-02 Research exposition (monographs, survey articles) pertaining to combinatorics 05C15 Coloring of graphs and hypergraphs
Full Text: