抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
グラフGの公平な彩色は,Gの頂点の彩色であり,2つの隣接頂点は同一に着色されず,さらに,色クラスサイズは,ほとんどの1で異なる。等価色数χ=(G)はこれに必要な色の最小数である。高密度ランダムグラフG(n,m)の等価色数を研究し,そこではm=[pnが2]と0<p<0.68が一定である。p=1/2が関数f(n)→∞であるかどうかのBollobの良く知られた疑問であり,長さf(n)の間隔の任意のシーケンスに対して,もしnが十分に大きいならば,G(n,m)の正常色数は少なくとも1/2の間隔の外側にある。Bollobは,これがf(n)=lognに対して保持されている可能性を提案した。等表色数に対して,類似質問に対する回答は負であることを示した。事実,χ=(G(n_j,m_j))=n/j,高い確率,すなわちχ_=(G(n_j,m_j))を持つ整数のサブシーケンス(n_j)_jが,厳密に1つの明示的に知られている値に集中している。これは,正常色数のような等価色数が絶対値,すなわちb=1/(1-p)でn/(2log_bn)に漸近的に等しいので,驚くほど狭い濃度を構成する。【JST・京大機械翻訳】