Sequence b-colorings in graphs
Marko Jakovac, Michael S. Lang
Source abstract
We introduce and begin the study of sequence b-colorings, a natural generalization of the classical notion of b-colorings introduced by Irving and Manlove in 1999. In a sequence b-coloring, each color class is required to contain a prescribed minimum number of color-dominating vertices (CDVs). We establish several fundamental properties of the associated parameters, prove that every sequence is realizable, and show that the problem of deciding whether a particular graph realizes a particular sequence is NP-complete. We also characterize the sequences realized by cycles, obtain results on regular graphs with prescribed girth, and investigate colorings requiring one additional CDV, including a characterization of connected graphs with chromatic number for which no such coloring exists.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.