Skip to content
Preprint

Sequence b-colorings in graphs

Sep 2026 · 0 citations · 11 references
Mathematics

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 $3$ for which no such coloring exists.

View source

Similar papers

Preprint Sep 2026

The Borowiecki-Broere Generalized Total Coloring Conjecture for Planar Graphs

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...

James Alexander Schreib · 0 citations
Open access Sep 2026

Acyclic (Δ + 2)-Edge Coloring of Toroidal Graphs Without Short Cycles

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...

Shu-Yi Chen, Dan-Jun Huang, Qiao-Jun Shu · 0 citations
Preprint Oct 2026

A note on the list chromatic number of two matroids

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...

Bence Garami · 0 citations
Preprint Sep 2026

Dominated Coloring of Some Classes of Perfect and Unicyclic Graphs

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...

R. Sneha, J. Geetha, K. Somasundaram · 0 citations
Preprint Sep 2026

Sub-quorum colorings of graphs

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(...

Hao Ma, Rafik Sahbi, Wen-Lin Zhang · 0 citations
Open access Sep 2026

The r-Hued Coloring of Complements of Cycles

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...

Guo-Zheng Zhang, Fengxia Liu · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.