On b-acyclic chromatic number of a graph
Open Access
- 26 December 2022
- journal article
- research article
- Published by Springer Nature in Computational and Applied Mathematics
- Vol. 42 (1) , 1-20
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)\rightarrow \{1,\ldots ,k\}$$ such that $$c(u)\ne c(v)$$ for any $$uv\in E(G)$$ and the induced subgraph on vertices of any two colors $$i,j\in \{1,\ldots ,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_{\textrm{b}}(G)$$ of G. We present several properties of $$A_{\textrm{b}}(G).$$ In particular, we derive $$A_{\textrm{b}}(G)$$ for several known graph families, derive some bounds for $$A_{\textrm{b}}(G),$$ compare $$A_{\textrm{b}}(G)$$ with some other parameters and generalize some influential tools from b-colorings to acyclic b-colorings.
Keywords
All Related Versions
Funding Information
- Narodowe Centrum Nauki (2020/37/B/ST1/03298)
- Faculty of Applied Mathematics AGH UST
- The Slovenian Research and Innovation Agency (J1-1693, J1-9109)
This publication has 30 references indexed in Scilit:
- -colouring outerplanar graphs with large girthDiscrete Mathematics, 2012
- Acyclic vertex coloring of graphs of maximum degree 5Discrete Mathematics, 2011
- b-chromatic number of cactiElectronic Notes in Discrete Mathematics, 2009
- Acyclic coloring of graphs of maximum degree five: Nine colors are enoughInformation Processing Letters, 2008
- Results on the Grundy chromatic number of graphsDiscrete Mathematics, 2006
- The b-chromatic number of a graphDiscrete Applied Mathematics, 1999
- Acyclic coloring of graphsRandom Structures & Algorithms, 1991
- On the equality of the grundy and ochromatic numbers of a graphJournal of Graph Theory, 1987
- The complexity of finding maximum disjoint paths with length constraintsNetworks, 1982
- On acyclic colorings of planar graphsDiscrete Mathematics, 1979