On b-acyclic chromatic number of a graph

DOI10.1007/S40314-022-02156-YarXiv2206.06478MaRDI QIDQ6401969FDOQ6401969

Authors: Marcin Anholcer, Sylwia Cichacz, Iztok Peterin

Publication date: 13 June 2022

Abstract: Let

G

be a graph. We introduce the acyclic b-chromatic number of

G

as an analogue to the b-chromatic number of

G

. An acyclic coloring of a graph

G

is a map

c : V (G) i g h t a r r o w 1, d o t s, k

such that

c (u) e q c (v)

for any

u v i n E (G)

and the induced subgraph on vertices of any two colors

i, j i n 1, d o t s, k

induces a forest. On the set of all acyclic colorings of

G

we define a relation whose transitive closure is a strict partial order. The minimum cardinality of its minimal element is then the acyclic chromatic number

A (G)

of

G

and the maximum cardinality of its minimal element is the acyclic b-chromatic number

A_{b} (G)

of

G

. We present several properties of

A_{b} (G)

. In particular, we derive

A_{b} (G)

for several known graph families, derive some bounds for

A_{b} (G)

, compare

A_{b} (G)

with some other parameters and generalize some influential tools from b-colorings to acyclic b-colorings.

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Structural characterization of families of graphs (05C75)

This page was built for publication: On b-acyclic chromatic number of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6401969)