円形着色

グラフ理論において、円彩色は、通常のグラフ彩色の改良版とみなせる彩色の一種である。と表されるグラフの円彩色数は、以下の定義のいずれかで与えられ、これらはすべて同等である（有限グラフの場合）。 ${\displaystyle G}$${\displaystyle \chi_{c}(G)}$

1. ${\displaystyle \chi_{c}(G)}$はすべての実数上の最小値であり、任意の 2 つの隣接する頂点がこの円に沿った距離の点に写像されるという特性を持つ、円周 1 の円への写像が存在する。${\displaystyle r}$${\displaystyle V(G)}$${\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}$

（特に 1 または 2 を使用すると）それは比較的簡単にわかりますが、実際には です。この意味で、円彩色数は通常の彩色数の改良版と見なします。 ${\displaystyle \chi _{c}(G)\leq \chi (G)}$${\displaystyle \lceil \chi _{c}(G)\rceil =\chi (G)}$

円形カラーリングはもともと Vince (1988) によって定義され、「スターカラーリング」と呼ばれていました。

色付けは、どこにも存在しないゼロフローという主題と双対であり、実際、円形の色付けには、円形フローという自然な双対概念があります。

円形完全グラフ
頂点	ん
エッジ	ｎ（ｎ − ２ｋ＋１）／２
胴回り	${\displaystyle \left\{{\begin{array}{ll}\infty &n=2k\\n&n=2k+1\\4&2k+2\leq n<3k\\3&{\text{otherwise}}\end{array}}\right.}$
彩度数	⌈n/k⌉
プロパティ	( n − 2 k + 1)正則 頂点推移 循環 ハミルトニアン
表記	${\displaystyle K_{n/k}}$
グラフとパラメータの表

となる整数に対して、円形完全グラフ（円形クリークとも呼ばれる）は、頂点集合が で、要素間の辺が距離 にあるグラフです。 つまり、頂点i は次のグラフに隣接しています。 ${\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.}$

${\displaystyle i+k,i+k+1,\ldots ,i+n-k{\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)、「グラフの円形着色」、グラフ着色、Contemp. Math.、vol. 352、プロビデンス、RI: Amer. Math. Soc.、pp. 123–137、doi :10.1090/conm/352/09、ISBN 978-0-8218-3458-9、MR  2076994。
• ヴィンス、A. (1988)、「スタークロマティック数」、グラフ理論ジャーナル、12 (4): 551–559、doi :10.1002/jgt.3190120411、MR  0968751。
• Zhu, X. (2001)、「円形彩色数、概観」、離散数学、229 (1–3): 371–410、doi :10.1016/S0012-365X(00)00217-X、MR  1815614。