论文标题
具有界树宽的挖掘物和挖掘物的产物的无环着色
Acyclic Coloring of Products of Digraphs and of Digraphs with Bounded Treewidth
论文作者
论文摘要
DICHRAPH $ G $的二分法是最小的整数$χ_a（g）$，因此可以将$ g $的顶点集分配为$χ_a（g）$集，每种都可以诱导一个acyclic subdigraph。这是经典色度图的概括。在这里，我们研究了笛卡尔，直接，强和词典产物的二分法数量，从而概括了对色的产品数量的一些经典效果。更具体地说，我们证明，以下不等式（已知具有色的图形数量）仍然适用于Dichromical digraphs：$χ_a（g \ square H）= \ max \ max \ {χ_a（g），χ_a（H）（H）\} $; $χ_a（g \ times h）\ le \ min \ {χ_a（g），χ_a（h）\} $;和$χ_a（g [h]）=χ_a（g [g [\ leftrightArow} {k} _k]）$，其中$ k =χ_a（h）$和$ \ overset {\ leftrightArrow} {k} {k} {k} _k $ degrestes the Complete dig digres the $ k $ k $ $ vertices。此外，我们研究了定向循环的产物，给出了$χ_a（\ Overset {\ rightarrow} {c} _n \ times \ times \ oftset {\ rightArrow} {c} _m）$和$χ_a（\ oftertem {\ oftarrow} {\ rightarrow} _n f bo \ overset {\ rightArrow} {c} _m）$每$ n，m $和$χ_a（\ overset {\ rightarrow} {c} {c} _n [h]）$对于每个正integer $ n $。后一个结果概括了\ cite {pp.16}中给出的结果，在$ n>χ_a（h）$时，它们给出了精确的值。我们还为Digraph $ g $的二分法数提供了上限，这是其基础图的树宽的函数，我们提出了一个{\ fpt} - 时间算法，该算法计算$ g $的二十五元数，当时是由$ g $的下层图的参数化。
The dichromatic number of a digraph $G$ is the smallest integer $χ_a(G)$ such that the vertex set of $G$ can be partitioned into $χ_a(G)$ sets, each of which induces an acyclic subdigraph. This is a generalization of the classic chromatic number of graphs. Here, we investigate the dichromatic number of the cartesian, direct, strong and lexicographic products, giving generalizations of some classic results on the chromatic number of products. More specifically, we prove that the following inequalities, known to hold for the chromatic number of graphs, still hold for the dichromatic number of digraphs: $χ_a(G\square H)=\max\{χ_a(G),χ_a(H)\}$; $χ_a(G\times H)\le \min\{χ_a(G),χ_a(H)\}$; and $χ_a(G[H]) = χ_a(G[\overset{\leftrightarrow}{K}_k])$, where $k =χ_a(H)$ and $\overset{\leftrightarrow}{K}_k$ denotes the complete digraph on $k$ vertices. In addition, we investigate the products of directed cycles, giving exact values for $χ_a(\overset{\rightarrow}{C}_n\times \overset{\rightarrow}{C}_m)$ and $χ_a(\overset{\rightarrow}{C}_n\boxtimes \overset{\rightarrow}{C}_m)$ for every $n,m$, and for $χ_a(\overset{\rightarrow}{C}_n[H])$ for every positive integer $n$. This latter result generalizes a result given in \cite{PP.16}, where they give exact values when $n>χ_a(H)$. We also provide a upper-bound to the dichromatic number of a digraph $G$ as a function of the treewidth of its underlying graph and we present an {\FPT}-time algorithm that computes the dichromatic number of $G$, when parameterized by treewidth of the underlying graph of $G$.
