平面上の曲線や線分について、様々な交差グラフの研究がなされている。
それらの交差グラフの一つにcontact graphというものがある。
contact graphは、互いに接触することはあるが、互いに交差することはないような
オブジェクトに対応する交差グラフである。
本発表では、contact graphの彩色数が、最大クリークの大きさの定数倍によって
押さえられることについて示した文献を紹介する。
参考文献："The maximal clique and colurability of curve contact graphs"
Back