円形着色

グラフ理論において、円形彩色とは、通常のグラフ彩色を洗練させたものと考えることができる彩色の一種である。グラフの円形彩色数とは、${\displaystyle G}$、と表記される${\displaystyle \chi _{c}(G)}$は、以下の定義のいずれかによって与えられることができ、これらはすべて（有限グラフの場合）同等である。

1. ${\displaystyle \chi _{c}(G)}$はすべての実数に対する下限です${\displaystyle r}$したがって、からへのマップが存在する${\displaystyle V(G)}$円周1の円で、隣接する2つの頂点が距離にある点に写像されるという性質を持つ。${\displaystyle \geq {\tfrac {1}{r}}}$この円に沿って。
2. ${\displaystyle \chi _{c}(G)}$は、すべての有理数に対する最小値である。${\displaystyle {\tfrac {n}{k}}}$したがって、からへのマップが存在する${\displaystyle V(G)}$環状基へ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$隣接する頂点が距離にある要素にマッピングされるという性質を持つ${\displaystyle \geq k}$離れて。
3. 有向グラフにおいて、サイクルの不均衡を宣言する${\displaystyle C}$である${\displaystyle |E(C)|}$時計回りのエッジ数と反時計回りのエッジ数のうち小さい方で割ります。有向グラフの不均衡をサイクルの最大不均衡と定義します。${\displaystyle \chi _{c}(G)}$は、方向の最小不均衡です。${\displaystyle G}$。

比較的容易にわかるのは、$\displaystyle \chi _{c}(G)\leq \chi (G)}$（特に1または2を使用する場合）しかし実際には${\displaystyle \lceil \chi _{c}(G)\rceil =\chi (G)}$このような意味において、私たちは円形彩色数を通常の彩色数の改良版と捉えています。

円形着色はもともとヴィンス（1988）によって定義され、彼はそれを「星形着色」と呼んだ。

彩色という概念は、どこにもゼロがない流れという主題と双対関係にあり、実際、円形彩色には自然な双対概念、すなわち円形の流れが存在する。

円形完全グラフ
頂点	n
エッジ	n ( n − 2 k + 1) / 2
周囲	${\displaystyle \left\{{\begin{array}{ll}\infty &n=2k\\n&n=2k+1\\4&2k+2\leq n<3k\\3&{\text{それ以外の場合}}\end{array}}\right.}$
彩色数	⌈n/k⌉
不動産	( n − 2k + 1)正則頂点推移的巡回ハミルトニアン
表記法	${\displaystyle K_{n/k}}$
グラフとパラメータの表

整数の場合${\displaystyle n,k}$そのため${\displaystyle n\geq 2k}$円形完全グラフ${\displaystyle K_{n/k}}$（円形クリークとも呼ばれる）は頂点集合を持つグラフである。${\displaystyle \mathbb {Z} /n\mathbb {Z} =\{0,1,\ldots ,n-1\}}$要素間の距離にあるエッジ${\displaystyle \geq k.}$ つまり、頂点iは、次の頂点に隣接しています。

${\displaystyle i+k,i+k+1,\ldots ,i+nk{\bmod {n}}.}$

${\displaystyle K_{n/1}}$は完全なグラフK _{n で}あり、${\displaystyle K_{2n+1/n}}$サイクルグラフは${\displaystyle C_{2n+1}.}$

上記の2番目の定義によれば、円形彩色とは、円形完全グラフへの準同型写像である。これらのグラフに関する重要な事実は、${\displaystyle K_{a/b}}$準同型を許容する${\displaystyle K_{c/d}}$かつその場合に限り$\displaystyle {\tfrac {a}{b}}\leq {\tfrac {c}{d}}.}$これは表記を正当化する。なぜなら、${\displaystyle {\tfrac {a}{b}}={\tfrac {c}{d}}}$それから${\displaystyle K_{a/b}}$そして${\displaystyle K_{c/d}}$これらは準同型である。さらに、これらの間の準同型順序は、完全グラフによって与えられる順序を、有理数に対応する稠密な順序に洗練する。$\displaystyle \geq 2$。 例えば

${\displaystyle K_{2/1}\to K_{7/3}\to K_{5/2}\to \cdots \to K_{3/1}\to K_{4/1}\to \cdots }$

または同等に

${\displaystyle K_{2}\to C_{7}\to C_{5}\to \cdots \to K_{3}\to K_{4}\to \cdots }$

図の例は、フラワースナークJ _5からK _5/2 ≈ C ₅への準同型として解釈でき、これは${\displaystyle K_{3}}$事実に対応して$\displaystyle \chi _{c}(J_{5})\leq 2.5<3.}$

• ランクカラーリング

• ナドルスキ、アダム（2004）「グラフの円形彩色」、グラフ彩色、現代数学、第 352巻、プロビデンス、ロードアイランド州：アメリカ数学会、123–137ページ、doi：10.1090/conm/352/09、ISBN  978-0-8218-3458-9MR 2076994​ 。
• Vince, A. (1988)、「スター彩色数」、Journal of Graph Theory、12 (4): 551–559、doi : 10.1002/jgt.3190120411、MR 0968751 。
• Zhu, X. (2001), "Circular chromatic number, a survey", Discrete Mathematics , 229 ( 1–3 ): 371–410 , doi : 10.1016/S0012-365X(00)00217-X , MR 1815614 。