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 $3$ for which no such coloring exists.
We prove the conjecture of Borowiecki and Broere that every finite simple planar graph admits a generalized total coloring with four colors: a proper vertex coloring with four colors together with an edge coloring with four colors in which each edge color class is a forest and no edge receives the color of either endpo...
An acyclic edge coloring of a graph G is a proper edge coloring such that G contains no bichromatic cycles. The acyclic chromatic index χa′(G) is the minimum number of colors required for an acyclic edge coloring. Fiamčik and Alon et al. independently conjectured that χa′(G)≤Δ+2 for every simple graph G with maximum de...
We study list coloring of common independent sets of two matroids. We construct a graphic matroid $M_1$ and a partition matroid $M_2$ with common chromatic number two and common list chromatic number three, showing that the two parameters need not be equal. This resolves a question raised by Kir\'aly, later stated as a...
The dominated coloring of a graph $G$ is a proper vertex coloring such that each color class is dominated by a vertex. The minimum number of colors required for a dominated coloring of a graph $G$ is called the dominated chromatic number of the graph $G$ and is denoted by $\chi_{dom}(G)$. A graph $G$ is said to be chro...
A sub-quorum coloring is a partial vertex coloring in which every colored vertex sees at least half of its colored closed neighborhood in its own color. We study the maximum number of colors $\psq(G)$ from structural, algorithmic and extremal viewpoints. Every $2$-independent set yields a sub-quorum coloring, so $\psq(...
Given a graph G , an r -hued coloring of G is a proper vertex coloring such that for every vertex v , the number of colors appearing in its neighborhood is at least min { d G ( v ) , r } , where d G ( v ) denotes the degree of v in G . The r -hued chromatic number χ r ( G ) is the smallest number of colors needed for a...