Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 32 min ago
PreprintCC BY 4.0arXiv

Sequence b-colorings in graphs

  • Marko Jakovac
  • Michael S. Lang
Open at sourcePDFDOICite

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.

Related

  1. Cayley graphs of abelian groups, circular colorings and discrete fundamental groups
    Kengo Enami, Takahiro Matsushita
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  2. On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
    Mohammed Lalou, Nader Mbarek, Abdallah Skender +1
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Optimal Kt-free list colorings and the Pollyanna property of graphs with no triangular wheel
    Hongyang Wang, Rong Wu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. Total eight-colorings of maximal planar graphs of maximum degree six
    Enqiang Zhu
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  5. Rich-neighbor 5-edge-colorings of subcubic graphs whose 3-vertices induce a matching
    Jiangxu Kong, Zhuming Lin, Yan Wang
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{jakovac2026sequence,
  title = {{Sequence b-colorings in graphs}},
  author = {Marko Jakovac and Michael S. Lang},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.08484},
  eprint = {2609.08484},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.08484},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Sequence b-colorings in graphs
AU  - Marko Jakovac
AU  - Michael S. Lang
PY  - 2026
DA  - 2026/09/08
PB  - arXiv
DO  - 10.48550/arxiv.2609.08484
UR  - https://arxiv.org/abs/2609.08484
AB  - 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.
ER  -