ترجمه فارسی مقاله رنگ آمیزی های گروهی شمارش چند جمله ای ها در نمودارها

چکیده

Jaeger et al. in 1992 introduced group coloring as the dual concept to group connectivity in graphs. Let $Γ$ be an Abelian group, $ f: E(G)\toΓ$ and $D$ an orientation of a graph $G$. A vertex coloring $c:V(G)\toΓ$ is a $(Γ, f)$-coloring if $c(v)-c(u)\ne f(e)$ for each edge $e=uv$ and the corresponding arc $D(e)=(u,v)$ directed from $u$ to $v$. We introduce the concept of $α$-compatible graphs and define the cycle-assigning polynomial $P(G, α; k)$ at $k$ in terms of $α$-compatible spanning subgraphs, where $α$ is an assigning of $G$ from its cycles to $\{0,1\}$. We prove that the cycle-assigning polynomial $P(G,α;k)$ equals the number of $(Γ,f)$-colorings for any Abelian group $Γ$ of order $k$ and $f:E(G)\toΓ$ such that the assigning $α_{D,f}$ induced by $f$ equals $α$. In particular, $P(G,α;k)$ is the classical chromatic polynomial if $α(C)=0$ for any cycle $C$ of $G$. Furthermore, we introduce the concept of $α$-compatible broken cycles and interpret $P(G,α;k)$ in terms of $α$-compatible spanning subgraphs that do not contain $α$-compatible broken cycles. This implies that the absolute value of the coefficient of $k^{r(G)-i}$ in $P(G,α;k)$ equals the number of $α$-compatible spanning subgraphs that have $i$ edges and contain no $α$-compatible broken cycles, which generalizes the Whitney’s Broken Cycle Theorem. Based on the combinatorial explanation, we establish a unified order-preserving relation from assignings to cycle-assigning polynomials. Finally, we show that for any loopless graphs $G$, the coefficients of the cycle-assigning polynomial $P(G,α;k)$ are nonzero and alternate in sign, and further conjecture that the sequence of absolute values of its coefficients is unimodal and log-concave.

چکیده به فارسی (ترجمه ماشینی)

جاگر و همکاران.در سال 1992 رنگ آمیزی گروه را به عنوان مفهوم دوگانه به اتصال گروه در نمودارها معرفی کرد.بگذارید $ γ $ یک گروه Abelian باشد ، $ f: e (g) \ toγ $ و $ d $ جهت گیری یک نمودار $ g $.رنگ آمیزی vertex $ c: v (g) \ toγ $ $ (γ ، f) $-رنگ آمیزی اگر $ c (v) -c (u) \ ne f (e) $ برای هر لبه $ e = uv $ $و قوس مربوطه $ d (e) = (u ، v) $ از $ u $ به $ v $ هدایت می شود.ما مفهوم نمودارهای سازگار با $ α $ را معرفی می کنیم و از چند جمله ای $ p (g ، α ؛ k) $ $ $ $ $ $ $ را از نظر زیرگرافهای پیچیده $ α $ $ تعریف می کنیم ، جایی که α α $ اختصاص دهنده است.از $ g $ از چرخه های خود به $ \ {0،1 \} $.ما ثابت می کنیم که چند جمله ای $ p (g ، α ؛ k) $ برابر با تعداد $ (γ ، f) $-رنگ آمیزی برای هر گروه abelian $ $ $ سفارش $ k $ و $ f: e (g) \ toγ $ به گونه ای که اختصاص $ α_ {d ، f} $ ناشی از $ f برابر است با $ α $.به طور خاص ، $ p (g ، α ؛ k) $ چند جمله ای کروماتیک کلاسیک اگر $ α (c) = 0 $ برای هر چرخه $ c $ g $ $ باشد.علاوه بر این ، ما مفهوم چرخه های شکسته سازگار با $ α $ را معرفی می کنیم و $ p (g ، α ؛ k) $ را از نظر زیرگرافهای پیچیده α α $ که حاوی چرخه های شکسته سازگار با $ α نیستند ، تفسیر می کنیم.این بدان معنی است که مقدار مطلق ضریب $ k^{r (g) -i} $ در $ p (g ، α ؛ k) $ برابر با تعداد زیرگرافهای سازگار با $ α $ است که دارای لبه های $ $ هستمو شامل هیچ چرخه شکسته سازگار با $ α $ ، که قضیه چرخه شکسته ویتنی را تعمیم می دهد.بر اساس توضیحات ترکیبی ، ما یک رابطه یکپارچه برای حفظ نظم را از تکالیف به چند جمله های تعیین کننده چرخه برقرار می کنیم.سرانجام ، ما نشان می دهیم که برای هر نمودار بدون حلقه $ g $ ، ضرایب چند جمله ای $ p (g ، α ؛ k) $ $ nonzero و متناوب در علامت هستند و بیشتر حدس می زنند که توالی مقادیر مطلق ضرایب آنUnimodal و Log-Concave است.