论文标题
关于统治编号的Grundy色素数的界限
Bounds for the Grundy chromatic number of graphs in terms of domination number
论文作者
论文摘要
对于任何图形$ g $，$ g $的grundy（或首先）的色数，由$γ（g）$表示（也是$χ_ {_ {_ {\ sf ff}}（g）$），定义为$ g $ g $ dertice vertices vertices dertices dertices derticing of the First-Fit（贪婪）使用的最大颜色数量。确定Grundy数字是$ NP $ - complete，并且在已知的图形参数方面获得$γ（g）$的界限是一个主动的研究主题。通过$ g $的星形分区，我们的意思是在$ v_1，\ ldots，v_k $中的$ v（g）$的任何分区，以使每个$ g [v_i] $都包含$ v_i $中任何其他顶点的顶点。在本文中，使用图形的星形分区，我们从统治数方面获得了Grundy数字的第一个上限。我们还从图形的统治数和周长方面证明了一些界限。
For any graph $G$, the Grundy (or First-Fit) chromatic number of $G$, denoted by $Γ(G)$ (also $χ_{_{\sf FF}}(G)$), is defined as the maximum number of colors used by the First-Fit (greedy) coloring of the vertices of $G$. Determining the Grundy number is $NP$-complete, and obtaining bounds for $Γ(G)$ in terms of the known graph parameters is an active research topic. By a star partition of $G$ we mean any partition of $V(G)$ into say $V_1, \ldots, V_k$ such that each $G[V_i]$ contains a vertex adjacent to any other vertex in $V_i$. In this paper using the star partition of graphs we obtain the first upper bounds for the Grundy number in terms of the domination number. We also prove some bounds in terms of the domination number and girth of graphs.
