2025/04/01 by Dragana Božović, Božović, Dragana, Daša Štesl +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Limits and Structures in Graph Theory #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2504.00553
A star coloring of a graph G is a proper coloring where vertices of every two color classes induce a forest of stars. A strict partial order is defined on the set of all star colorings of G. We introduce the star b-chromatic number Sb(G), analogous to the b-chromatic number, as the maximum number of colors in a minimum element of the mentioned order. We present several combinatorial properties of Sb(G), compute the exact value for Sb(G) for several known families and compare Sb(G) with several invariants naturally connected to Sb(G).