Upper bound graphとposetの関連について

Simplicial vertexの性質に注目することにより,グラフG及びGの補グラフGが共に,upper bound graphである為の特徴付けとしてGが次の(1),(2)の条件のいずれかを満たすsplite graphであることが得られた。ただし,V(G)=Ktsで,Kはcliquo,Sは独立集合である。(1)Kにsimplicial verlexが存在する。(2)Kの任意の辺e={u, v}に対して,u, v両方と隣接しているSの点心が存在し、Sの任意の2点x,yに対して,x, yの両方と隣接していないKの点心が存在する。Double bound graphに関しては,任意のグラフGに対して,Gを誘導部分グラフとして含むDouble bound graphが存在することがわかり,禁止部分グラフの言葉では,Double boand graphが特徴付けれないことがわかった。また連結な2部グラフGに対して,G,Eが共にDouble bound graphであることと,GがKm, nKm,-Ek, l, m, n, Ek, l-Er, sのいずれかであることが同値であることがわかった。ここで,Ek,lはGの辺部分集合で〈Ek,l〉_BがKk, lと同形なもののことであり,Km, nn-Ek, lは辺集合がE(Km, n)-Ek, lなる連結グラフ,Km, n-Ek, l-Er, sは辺集合がE(Km, n)-Ek, l-Er, sで,V(〈Ek, l〉_E)のV(〈Ec,s〉_E)=φなる連結グラフのことである。さらに,splite graph Gに関して,G ,Gが共にDouble bound graphであるための特徴付けや,極大元や極小元の集合のantichain性に注目することにより,strict Double bound graphの特徴付けを得た。posetからのアプローチにおいて,upper bound graphを特徴付けるclique coverがposetのcrder indealによるcoverに対応していることに注目し,upper bound graphが同形であるposet間の変換の特徴付けが得られた。またDouble bound graphについても同様の結果が得られた。simplicial vertex等のグラフ上の幾何学的性質を検討することにより,曲面上のLinear Arboricity to convex polygonへの分割に関する結果も得られている。

Simplicial vertexの性質に注目することにより,グラフG及びGの補グラフGが共に,upper bound graphである為の特徴付けとしてGが次の(1),(2)の条件のいずれかを満たすsplite graphであることが得られた。ただし,V(G)=Ktsで,Kはcliquo,Sは独立集合である。(1)Kにsimplicial verlexが存在する。(2)Kの任意の辺e={u, v}に対して,u, v両方と隣接しているSの点心が存在し、Sの任意の2点x,yに対して,x, yの両方と隣接していないKの点心が存在する。Double bound graphに関しては,任意のグラフGに対して,Gを誘導部分グラフとして含むDouble bound graphが存在することがわかり,禁止部分グラフの言葉では,Double boand graphが特徴付けれないことがわかった。また連結な2部グラフGに対して,G,Eが共にDouble bound graphであることと,GがKm, nKm,-Ek, l, m, n, Ek, l-Er, sのいずれかであることが同値であることがわかった。ここで,Ek,lはGの辺部分集合で〈Ek,l〉_BがKk, lと同形なもののことであり,Km, nn-Ek, lは辺集合がE(Km, n)-Ek, lなる連結グラフ,Km, n-Ek, l-Er, sは辺集合がE(Km, n)-Ek, l-Er, sで,V(〈Ek, l〉_E)のV(〈Ec,s〉_E)=φなる連結グラフのことである。さらに,splite graph Gに関して,G ,Gが共にDouble bound graphであるための特徴付けや,極大元や極小元の集合のantichain性に注目することにより,strict Double bound graphの特徴付けを得た。posetからのアプローチにおいて,upper bound graphを特徴付けるclique coverがposetのcrder indealによるcoverに対応していることに注目し,upper bound graphが同形であるposet間の変換の特徴付けが得られた。またDouble bound graphについても同様の結果が得られた。simplicial vertex等のグラフ上の幾何学的性質を検討することにより,曲面上のLinear Arboricity to convex polygonへの分割に関する結果も得られている。