Intersection Graphの研究

点击翻译按钮获取中文摘要

Antichain Intersection number Wai(G)がWai(G)=【symmetry】:^<min>tccofg{1【symmetry】1+1i(【symmetry】)}(i(()SY.sym.〔))={S(V)1^〓u【thermodynamics】V;S(V)≦S(u)})とtotal Clique Cover【symmetry】を用いてとらえられることがわかった。この結果を用いて,2ーcell embedable graph Gに対して,Wai(G)≦(1ー1/(X(G^*)))・IV(G^*)1であり,平面グラフに対して,Wai(G)≦4/3(IVG)1ー2)であり,極大平面的グラフに対して,Wai(G)≦IV(G)1ー2という評価が得られている。ここで,G^*はGの双対グラフのことであり、X(G^*)はG^*は染色数のことである。さらに,Kaーfree,rーregular graph G(IV(G)≧4,r≧3)に対して,Wai(G)=Wm(G)+IEs(G)1であるとこも前述の結果より得られている。ただし,Wm(G)=【symmetry】:^<min>tccofGl【symmetry】1であり,Es(G)={U,V}∈E(G)|N(u)ー{V}=N(V)ー{u}}である。また,一般の正則グラフに対しては,2ー正則グラフGに対して,Wai(G)=IE(G)|,3ー正則グラフGに対して,Wai(G)=3角形に含まれないGの辺の本数+Gの三角形の個数,であることが得られ,4,5ー正則グラフに対しても同様の結果が得られた。Wai(Kn+Ne)を求めるために,Intersecting familyに関するテクニックを応用しようとしたことがら派生した結果として,最小元(1)を持つposetpに関するshifted complex FとFの交差部分剤yに対して,1y1≦#{F∈F;(1)∈F}なることが得られた。W(G)を決定することがNP完全であることがS.Poljak等によって得られていることがわかり,Wai(G)及びWui(G)を決定することについてもNP完全であることが予想され目下このことについて研究中である。さらに,uniform intersection number Wui(G)をtotal clique coverからとらえることについても研究中である。