着色不良
同じ色の近傍点の許容数によるグラフの色付け

数学分野であるグラフ理論において、彩色とはグラフの頂点、辺、面に色やラベルを割り当てることを指します。欠陥彩色は適切な頂点彩色の変形です。適切な頂点彩色では、隣接する頂点が同じ色にならないように頂点が彩色されます。一方、欠陥彩色では、ある程度まで頂点が同じ色で隣接することが許容されます。

歴史

欠陥彩色は、Andrews と Jacobson [1] 、 Harary と Jones、および Cowen、Cowen と Woodall [2]によってほぼ同時に導入されました。この彩色と関連する彩色の調査は Marietjie Frick [ 3]によって提供されています。 Cowen、Cowen と Woodall [2] は、曲面に埋め込まれたグラフに焦点を当て、すべての平面グラフが ( k、d )-彩色可能であるようなすべてのkとdの完全な特徴付けを与えました。つまり、すべての平面グラフが (1、 d )-または (2、d )-彩色可能であるようなd は存在しません。(3、 1)-彩色可能ではない平面グラフは存在しますが、すべての平面グラフは (3、 2)-彩色可能です。 4 色定理によって暗示される (4、 0)-彩色と一緒に、これは平面の欠陥彩色数を解決します。 Poh [4]と Goddard [5]は、任意の平面グラフには各色クラスが線型フォレストとなる特殊な (3,2)-彩色があり、これは Woodall のより一般的な結果から得られることを示した。一般的な曲面については、各種数 に対して、種数 の曲面上のすべてのグラフが (4, k )-彩色可能であるような が存在することが示された。[2]これはDan Archdeaconによって(3, k )-彩色可能に改良された。[6]一般的なグラフについては、 1960 年代のLászló Lovász の結果で何度も再発見されている[7] [8] [9] は、最大次数 ∆ の欠陥彩色グラフに対してO(∆E) -時間のアルゴリズムを提供している。 グラム ≥ 0 {\displaystyle g\geq 0} け ＝ け （ グラム ） {\displaystyle k=k(g)} グラム {\displaystyle g}

定義と用語

着色不良

グラフGの( k ,  d )-彩色とは、各頂点vが最大でd 個の隣接頂点を持つようなk色による頂点彩色である。kは正の整数（ k = 0の場合を考慮する必要はない）、d は非負の整数とする。したがって、( k , 0 )-彩色は適切な頂点彩色と同義である。[10]

d-色数に欠陥がある

Gが( k , d )-色可能であるために必要な最小の色数kはd-欠陥色数と呼ばれる。[11] χ d （ G ） {\displaystyle \chi _{d}(G)}

グラフクラスGにおいて、Gの欠陥彩色数は、ある整数dに対してG内のすべてのグラフが ( k , d )-彩色可能であるような最小の整数kである。例えば、平面グラフのクラスの欠陥彩色数は 3 である。これは、すべての平面グラフが (3,2)-彩色可能であり、任意の整数dに対して (2, d )-彩色不可能な平面グラフが存在するからである。

頂点の不適切さ

グラフGの頂点彩色をcとする。Gの頂点vの彩色cに関する不適正度は、vの近傍の頂点のうちvと同じ色を持つ頂点の数である。vの不適正度が0 の場合、v は適切に彩色されていると言われる。[2]

頂点彩色の不適切さ

cをグラフGの頂点彩色とする。cの不適正度はGのすべての頂点の不適正度の最大値である。したがって、適切な頂点彩色の不適正度は 0 である。[2]

例

d = 0, 1, 2 の場合の 5 つの頂点の閉路の不完全な着色の例

5頂点上の閉路の不完全な彩色例を図に示す。最初の部分図は、正しい頂点彩色、すなわち( k ,0)-彩色の例である。2番目の部分図は( k ,1)-彩色の例であり、3番目の部分図は( k ,2)-彩色の例である。以下の点に注意されたい。 C 5 {\displaystyle C_{5}}

χ 0 （ C 5 ） ＝ χ （ C 5 ） ＝ 3 {\displaystyle \chi _{0}(C_{5})=\chi (C_{5})=3}

χ 1 （ C 5 ） ＝ 3 {\displaystyle \chi _{1}(C_{5})=3}

χ 2 （ C n ） ＝ 1 ; た n ∈ 北 {\displaystyle \chi _{2}(C_{n})=1;\forall n\in \mathbb {N} }

プロパティ

  • グラフGが ( k , d )-彩色可能であるためには、 Gのすべての連結成分が ( k , d )-彩色可能であることが必要であるため、連結グラフを考慮すれば十分である。[2]
  • グラフ理論的に言えば、適切な頂点彩色における各色クラスは独立集合を形成するが、欠陥彩色における各色クラスは最大次数dのサブグラフを形成する。[12]
  • グラフが( k , d )-彩色可能であるならば、k′≥kかつd′ ≥dとなるような各(k′,d′)のペアに対して( k ′ , d′ ) -彩色可能である。[2]

いくつかの結果

毎外平面グラフ(2,2)色可能である

証明：を連結外平面グラフとする。を の任意の頂点とする。から の距離にあるの頂点の集合とする。によって誘導される部分グラフをとする。に次数3以上の頂点が含まれると仮定すると、 は を部分グラフとして含む。次に、 のすべての辺を縮約して新しいグラフ を得る。 G {\displaystyle G} v 0 {\displaystyle v_{0}} G {\displaystyle G} V 私 {\displaystyle V_{i}} G {\displaystyle G} 私 {\displaystyle i} v 0 {\displaystyle v_{0}} G 私 {\displaystyle G_{i}} ⟨ V 私 ⟩ {\displaystyle \langle V_{i}\rangle } V 私 {\displaystyle V_{i}} G 私 {\displaystyle G_{i}} K 1 、 3 {\displaystyle K_{1,3}} V 0 ∪ V 1 ∪ 。 。 。 ∪ V 私 − 1 {\displaystyle V_{0}\cup V_{1}\cup ...\cup V_{i-1}} G ′ {\displaystyle G'}

⟨ V 0 ∪ V 1 ∪ 。 。 。 ∪ V 私 − 1 ⟩ {\displaystyle \langle V_{0}\cup V_{1}\cup ...\cup V_{i-1}\rangle } のは連結されており、 のすべての頂点はの頂点に隣接しています。したがって、上で述べたすべての辺を縮約することによって、のサブグラフは、 のすべての頂点に隣接する単一の頂点に置き換えられます。したがって、 はサブグラフとして を含みます。しかし、外平面グラフのすべてのサブグラフは外平面グラフであり、外平面グラフの辺を縮約することによって得られるすべてのグラフは外平面グラフです。これはが外平面グラフであることを意味し、矛盾しています。したがって、どのグラフにも次数 3 以上の頂点は含まれず、は ( k , 2)-彩色可能であることを意味します。 のどの頂点も または のどの頂点にも隣接していません。したがって、 の頂点は、が奇数の場合は青、偶数の場合は赤に彩色できます。したがって、 の (2,2)-彩色が生成されました。[2] G ′ {\displaystyle G'} V 私 {\displaystyle V_{i}} V 私 − 1 {\displaystyle V_{i-1}} G ′ {\displaystyle G'} ⟨ V 0 ∪ V 1 ∪ 。 。 。 ∪ V 私 − 1 ⟩ {\displaystyle \langle V_{0}\cup V_{1}\cup ...\cup V_{i-1}\rangle } G ′ {\displaystyle G'} V 私 {\displaystyle V_{i}} G ′ {\displaystyle G'} K 2 、 3 {\displaystyle K_{2,3}} K 2 、 3 {\displaystyle K_{2,3}} G 私 {\displaystyle G_{i}} G {\displaystyle G} V 私 {\displaystyle V_{i}} V 私 − 1 {\displaystyle V_{i-1}} V 私 + 1 、 私 ⩾ 1 {\displaystyle V_{i+1},i\geqslant 1} V 私 {\displaystyle V_{i}} 私 {\displaystyle i} G {\displaystyle G}

系：すべての平面グラフは(4,2)-彩色可能である。 これは、が平面グラフであるならば、すべての は（上記と同じ）外平面グラフであるということと同じである。したがって、すべてのは(2,2)-彩色可能である。したがって、 の各頂点は、 が偶数であれば青または赤、 が奇数であれば緑または黄色に彩色でき、したがって の(4,2)-彩色が得られる。 G {\displaystyle G} G 私 {\displaystyle G_{i}} G 私 {\displaystyle G_{i}} V 私 {\displaystyle V_{i}} 私 {\displaystyle i} 私 {\displaystyle i} G {\displaystyle G}

完全なマイナーを除外したグラフ

任意の整数に対して、マイナーグラフを持たない任意のグラフが-色可能であるような整数が存在する。[13] t {\displaystyle t} 北 {\displaystyle N} G {\displaystyle G} K t {\displaystyle K_{t}} （ t − 1 、 北 ） {\displaystyle (t-1,N)}

計算の複雑さ

欠陥彩色は計算的に困難である。与えられたグラフが(3,1)-彩色を許容するかどうかを判定することは、たとえ最大頂点次数が6のグラフや最大頂点次数が7の平面グラフであっても、NP完全である。 [14] G {\displaystyle G} G {\displaystyle G}

アプリケーション

欠陥色彩の応用例としては、頂点がジョブ（例えばコンピュータシステム上のユーザー）を表し、辺が競合（同じファイルへのアクセスを必要とすること）を表すスケジューリング問題が挙げられます。欠陥を許容するということは、競合の閾値をある程度許容することを意味します。各ユーザーは、システム上で競合するユーザーが2人いる場合、データの取得に発生する最大の速度低下は許容範囲内と見なしますが、3人以上の場合は許容範囲外と見なします。[15]

注記

  1. ^ アンドリュース, ジェームズ・A.; ジェイコブソン, マイケル・S. (1985). 「彩色数の一般化について」.コングレ・ヌマー. 47 : 33–48 .
  2. ^ abcdefgh Cowen, LJ ; Cowen, RH; Woodall, DR (2006年10月3日). 「曲面グラフの欠陥着色：有界価数部分グラフへの分割」. Journal of Graph Theory . 10 (2): 187– 195. doi :10.1002/jgt.3190100207.
  3. ^ Frick, Marietjie (1993). 「(M, k)-カラーリングの概説」. Annals of Discrete Mathematics. Vol. 55. pp.  45– 57. doi :10.1016/S0167-5060(08)70374-1. ISBN 9780444894410。
  4. ^ Poh, KS (1990年3月). 「平面グラフの線形頂点樹状性について」. Journal of Graph Theory . 14 (1): 73– 75. doi :10.1002/jgt.3190140108.
  5. ^ ゴダード, ウェイン (1991年8月7日). 「平面グラフの非巡回着色」.離散数学. 91 (1): 91–94 . doi : 10.1016/0012-365X(91)90166-Y .
  6. ^ アーチディーコン、ダン(1987). 「曲面グラフの欠陥着色に関する注記」.グラフ理論ジャーナル. 11 (4): 517– 519. doi :10.1002/jgt.3190110408.
  7. ^ ベルナルディ、クラウディオ（1987年3月）「グラフの頂点彩色に関する定理について」離散数学. 64 (1): 95–96 . doi : 10.1016/0012-365X(87)90243-3 .
  8. ^ Borodin, OV; Kostochka, AV (1977年10～12月). 「グラフの次数と密度に依存するグラフの彩色数の上限について」. Journal of Combinatorial Theory . Series B. 23 ( 2～ 3): 247～ 250. doi : 10.1016/0095-8956(77)90037-5 .
  9. ^ ローレンス、ジム (1978). 「グラフの頂点集合をより小さな次数のサブグラフで覆う」.離散数学. 21 (1): 61– 68. doi : 10.1016/0012-365X(78)90147-4 .
  10. ^ Cowen, L. ; Goddard, W. ; Jesurum, CE (1997). 「欠陥カラーリングの再考」. Journal of Graph Theory . 24 (3): 205– 219. CiteSeerX 10.1.1.52.3835 . doi :10.1002/(SICI)1097-0118(199703)24:3<205::AID-JGT2>3.0.CO;2-T. 
  11. ^ Frick, Marietjie; Henning, Michael (1994年3月). 「グラフの欠陥着色に関する極限結果」.離散数学. 126 ( 1–3 ): 151–158 . doi : 10.1016/0012-365X(94)90260-7 .
  12. ^ Cowen, LJ , Goddard, W., Jesurum, CE 1997. 欠陥のある色付け. 第8回ACM-SIAM離散アルゴリズムシンポジウム（米国ルイジアナ州ニューオーリンズ、1997年1月5～7日）の議事録. 離散アルゴリズムシンポジウム. Society for Industrial and Applied Mathematics, Philadelphia, PA, 548–557.
  13. ^ Edwards, Katherine; Kang, Dong Yeap; Kim, Jaehoon; Oum, Sang-il ; Seymour, Paul (2015). 「Hadwigerの予想の類似例」. SIAM Journal on Discrete Mathematics . 29 (4): 2385– 2388. arXiv : 1407.5236 . doi :10.1137/141002177. S2CID  12157191.
  14. ^ アンジェリーニ、パトリツィオ;ベコス、マイケル。デ・ルーカ、フェリーチェ。ディディモ、ウォルター。カウフマン、マイケル。コボウロフ、スティーブン。モンテッキアーニ、ファブリツィオ。ラフトポロウ、クリサンティ。ロゼッリ、ヴィンチェンツォ。シンボニス、アントニオス (2017)。 「欠陥のある頂点カラーリング」。グラフ アルゴリズムとアプリケーションのジャーナル。21 (3): 313–340 .土井: 10.7155/jgaa.00418。
  15. ^ Cowen, LJ ; Goddard, W.; Jesurum, CE (1997年1月5日). 「欠陥のある色付け」. SODA '97 Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms : 548– 557. ISBN 9780898713909。

参考文献

  • アンドリュース、ジェームズ・A.；ジェイコブソン、マイケル・S. （1985）「彩色数の一般化について」、コングレ・ヌマー、47：33-48
  • イートン、ナンシー・J.; ハル、トーマス (1999)、「平面グラフの欠陥リスト彩色」、Bull. Inst. Combin. Appl、25 : 79– 87、CiteSeerX  10.1.1.91.4722
  • ウィリアム・W.; ハル・トーマス (2002)、「欠陥のある円形着色」、オーストラリア学会誌、26 : 21–32、CiteSeerX  10.1.1.91.4722
  • フリック、マリエットジー; ヘニング、マイケル (1994年3月)、「グラフの欠陥着色に関する極限結果」、離散数学、126 ( 1–3 ): 151– 158、doi : 10.1016/0012-365X(94)90260-7
  • LJ Cowen、W. Goddard、CE Jesurum（1997年1月5日）、「欠陥のある色付け」、SODA '97 Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms：548– 557、ISBN 9780898713909
  • LJ Cowen; RH Cowen; DR Woodall (2006年10月3日)、「曲面グラフの欠陥着色：有界価数部分グラフへの分割」、Journal of Graph Theory、10 (2): 187– 195、doi :10.1002/jgt.3190100207
  • アーチディーコン、ダン（1987）「曲面グラフの欠陥着色に関する注記」、グラフ理論ジャーナル、11（4）：517-519、doi：10.1002/jgt.3190110408
  • Poh, KS (1990年3月)、「平面グラフの線形頂点樹状性について」、Journal of Graph Theory、14 (1): 73– 75、doi :10.1002/jgt.3190140108
  • ゴダード、ウェイン（1991年8月7日）「平面グラフの非巡回着色」、離散数学、91（1）：91-94、doi：10.1016/0012-365X（91）90166-Y
  • ボロディン, OV; コストカ, AV (1977年10月～12月)「グラフの次数と密度に依存するグラフの彩色数の上限について」、Journal of Combinatorial Theory、シリーズB、23 ( 2～ 3): 247～ 250、doi : 10.1016/0095-8956(77)90037-5
  • ローレンス、ジム（1978）、「グラフの頂点集合をより小さな次数のサブグラフで覆う」、離散数学、21（1）：61-68、doi：10.1016/0012-365X（78）90147-4
  • アンジェリーニ、パトリツィオ。ベコス、マイケル。デ・ルーカ、フェリーチェ。ディディモ、ウォルター。カウフマン、マイケル。コボウロフ、スティーブン。モンテッキアーニ、ファブリツィオ。ラフトポロウ、クリサンティ。ロゼッリ、ヴィンチェンツォ。 Symvonis、Antonios (2017)、「Vertex-Coloring with Defects」、Journal of Graph Algorithms and Applications、21 (3): 313–340、doi : 10.7155/jgaa.00418
「https://en.wikipedia.org/w/index.php?title=欠陥色&oldid=1312271994」より取得