论文标题
在b-酰基色的图上
On b-acyclic chromatic number of a graph
论文作者
论文摘要
令$ g $为图。我们介绍了$ g $的无环b-chromation数量，以类似于$ g $的b奇异数。图$ g $的无环着色是地图$ c：v（g）\ rightarrow \ {1，\ dots，k \} $，以至于$ c（u）\ neq c（n neq c（v）$ for e（g）中的任何$ uv \ in e（g）$ in（g）$和诱导的两种颜色$ i， 森林。在$ g $的所有无环着色的集合中，我们定义了一种关系，其及时关闭是严格的部分订单。其最小元素的最小基数是$ g $的无环色$ a（g）$ a（g）$ a（g）$ g $，其最小元素的最大基数是无环b-chrostic number $ a_b（g）$ g $ $ g $。我们介绍了$ a_b（g）$的几个属性。特别是，我们为几个已知的图形家族得出$ a_b（g）$，为$ a_b（g）$得出某些界限，将$ a_b（g）$与其他一些参数进行比较，并将某些有影响力的工具从b-colorings到acyclic b-colorings进行概括。
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,\dots,k\}$ such that $c(u)\neq c(v)$ for any $uv\in E(G)$ and the induced subgraph on vertices of any two colors $i,j\in \{1,\dots,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.
