区間カラーリング

グラフ理論において、順序付きグラフの区間彩色数 は、（線形順序付き）頂点集合を、同じ区間に属する2つの頂点が隣接しないように分割できる区間の最小数である。^{[1] [2]}${\displaystyle \chi _{<}(H)}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle H}$

定義と基本的な性質

順序付きグラフとは、頂点集合 上に指定された線形順序を持つグラフである。順序付きグラフ において、区間彩色とは、を連続する頂点の独立した集合（区間または部分と呼ばれる）に分割することである。区間彩色数は、 の任意の区間彩色における部分の最小数である。^[2]${\displaystyle G}$ ${\displaystyle V(G)}$ ${\displaystyle H}$ ${\displaystyle V(H)}$ ${\displaystyle \chi _{<}(H)}$ ${\displaystyle H}$

区間彩色の部分は独立集合なので、

${\displaystyle \chi _{<}(H)\geq \chi (H)}$ 、

ここで、 は常彩色数である。^[2]${\displaystyle \chi (H)}$

順序付きグラフが区間k彩色（またはk-ichromatic）と呼ばれるのは、次の場合である。^[2]${\displaystyle \chi _{<}(H)=k}$

計算の複雑さ

特に興味深いのは、区間彩色数が容易に計算できることです。単純な貪欲アルゴリズムを用いることで、グラフの頂点集合を独立区間に分割する最適な方法を効率的に見つけることができます。^[1]これは、グラフの彩色数の通常の計算とは対照的です。グラフの彩色数では、近似値を求めることさえNP困難な作業です。 ${\displaystyle H}$ ${\displaystyle \chi _{<}(H)}$

与えられたグラフとその同型グラフでは、彩色数は同じままですが、区間彩色数は頂点集合の順序によって異なる場合があります。^[2]${\displaystyle H}$

極端理論

パックとタルドスは、区間彩色数と極値グラフ理論を関連付ける基本定理を証明した。^[1]

任意の順序付きグラフ について、頂点を 持つ 自由順序付きグラフが持つことができる辺の最大数は次のとおりです。${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle n}$

${\displaystyle ex_{<}(n,H)=\left(1-{\frac {1}{\chi _{<}(H)-1}}\right){\binom {n}{2}}+o(n^{2})}$

この定理は、以下の禁制順序付き部分グラフの族にも自然に拡張される。^[1]${\displaystyle {\mathcal {H}}}$

${\displaystyle \chi _{<}({\mathcal {H}}):=\min\{\chi _{<}(H)\mid H\in {\mathcal {H}}\}}$

禁断のパターンとの関係

区間彩色数は、順序付きグラフと零一行列の禁制パターン問題において重要な役割を果たします。2-icolor順序付きグラフの場合、極値関数の式から二次項が消えるため、極値問題は特に興味深いものとなります。^[1]これらは零一行列で表すことができ、頂点は と列挙され、すべての辺は を持つ辺と を持つ辺に接続されます。^[1]${\displaystyle v_{1}<v_{2}<\ldots <v_{n}<v_{n+1}<\ldots <v_{n+m}}$ ${\displaystyle v_{i}}$ ${\displaystyle i\leq n}$ ${\displaystyle v_{j}}$ ${\displaystyle j>n}$

禁制パターン問題は、単位距離グラフ問題、平面線分中心問題、ダベンポート・シンツェル列の発見など、離散幾何学のいくつかの問題に関連しています。^[1]

参照

• 順序付きグラフ
• グラフの色付け
• ラムゼイ理論
• 極値グラフ理論

参考文献

1. Pach, János ; Tardos, Gábor (2005)、「禁止パターンと単位距離」、Mitchell, Joseph SB; Rote, Günter (編)、Proceedings of the 21st ACM Symposium on Computational Geometry、ピサ、イタリア、2005年6月6日～8日、Association for Computing Machinery、pp.  1～ 9、doi :10.1145/1064092.1064096、MR  2460341、S2CID  18752227
2. Neidinger, Dana; West, Douglas B. (2019年9月). 「区間2彩色順序グラフのラムゼー数」.グラフと組合せ論. 35 (5): 1065–1076 . arXiv : 1805.05900 . doi :10.1007/s00373-019-02057-8. ISSN  0911-0119.