论文标题
带有受限双色子图的图形颜色：I。无环，星和树宽的颜色
Graph colorings with restricted bicolored subgraphs: I. Acyclic, star, and treewidth colorings
论文作者
论文摘要
我们表明，对于任何固定的整数$ m \ geq 1 $，最大度$δ$的图都具有$ o（δ^{（m+1）/m}）$颜色的颜色，其中每个连接的双色子格式最多包含$ m $ edges。该结果统一了以前已知的上限在某些类型的图形色素的颜色数量上，包括$ o（δ^^{3/2}）$颜色的颜色和acyclic颜色，其中$ o（Δ^^{4/3}）$颜色就足够了。我们的证明使用了Alon，McDiarmid和Reed的概率方法。该结果还提供了以前未知的上限，包括以下事实：最高度$δ$具有$ o（δ^{9/8}）$颜色的适当着色，其中每个双色子图都是平面，以及$ o（δ^^{13/12}）的适当着色，每个双色颜色在每个双色颜色中，每个双色颜色在每个Bicolored subgraph int yew $ $ $ $ 3 $ 3 $ 3 $ 3 $ 3 $ 3 $ 3 $ 3 $ 3 $ 3 $ 3.
We show that for any fixed integer $m \geq 1$, a graph of maximum degree $Δ$ has a coloring with $O(Δ^{(m+1)/m})$ colors in which every connected bicolored subgraph contains at most $m$ edges. This result unifies previously known upper bounds on the number of colors sufficient for certain types of graph colorings, including star colorings, for which $O(Δ^{3/2})$ colors suffice, and acyclic colorings, for which $O(Δ^{4/3})$ colors suffice. Our proof uses a probabilistic method of Alon, McDiarmid, and Reed. This result also gives previously unknown upper bounds, including the fact that a graph of maximum degree $Δ$ has a proper coloring with $O(Δ^{9/8})$ colors in which every bicolored subgraph is planar, as well as a proper coloring with $O(Δ^{13/12})$ colors in which every bicolored subgraph has treewidth at most $3$.
