2016/07/28 by Ana Silva, Silva, Ana
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1607.08453
arxiv created 2016/08/30 · arxiv updated 2016/08/31
Given a proper coloring f of a graph G, a b-vertex in f is a vertex that is adjacent to every color class but its own. It is a b-coloring if every color class contains at least one b-vertex, and it is a fall-coloring if every vertex is a b-vertex. The b-chromatic number of G is the maximum integer b(G) for which G has a b-coloring with b(G) colors, while the fall-chromatic number and the fall-acromatic number of G are, respectively, the minimum and maximum integers f1(G),f2(G) for which G has a fall-coloring. In this article, we explore the concepts of b-homomorphisms and Type II homomorphisms, which generalize the concepts of b-colorings and fall-colorings, and present some meta-theorems concerning products of graphs. As a result, we derive some previously known facts about these metrics on graph products. We also give a negative answer to a question posed by Kaul and Mitillos about fall-colorings of perfect graphs.