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.

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