グラフの色数を見つけ、その数値を使って有効な色付けを行うためのアルゴリズムを開発しています。この目的のために、私は、可能な答えKを見つけるためのバイナリサーチを使用し、遺伝的アルゴリズムを使用してKが可能かどうかをチェックする。問題は、有彩色数が不均一に分布していることです。たとえば、頂点が1000のグラフの場合、その色数は100以下になる可能性が最も高いです。私のバイナリ検索では、左境界と右境界の中間を分割する必要はありませんが、数分布。このディストリビューションについての情報をどこから得ることができるかを知っていますか？私はいくつかの詳細を教えているソースを見つけましたが、ノードが10個以下のグラフの場合：http://keithbriggs.info/cgt.htmlです。グラフ分布の色数
一定の大きさのグラフには有意味な分布がありません。実際、このような分布を定義するには、まず入力グラフに分布を定義する必要があります。私は何を意味するか説明します。まず、P_Gを入力グラフの分布と定義します。次に、有彩色数をグラフを整数に写像する確率変数Xと考える。最後に、P_X（X = k）= P_G（{G、f（G）= k}）でP_Xを呼び出すと、X上の分布が得られます。面倒な書式設定についてお詫び申し上げます。これが意味をなさないかどうか教えてください。
私は、（1）入力グラフP_Gに分布していない可能性があり、（2）閉じた形を得るのが難しいため、有彩色数の分布が望ましいとは思わないあなたがP_Gを持っていたとしてもP_X。単純なErdos Renyiランダムグラフモデルであっても、予想される色数は分かりません。
使用できる境界は、（1）最大次数+ 1、（2）色数が少なくとも最大クリークのサイズです。調べるかもしれないseveral other boundsがありますが、これはホフマン境界ですが、これを得るには固有値の計算が必要なので難しいかもしれません。私はあなたのベスト・ベットは、（1）グラフをより小さな重なり合ったサブグラフに分解し、それらを着色し、（2）着色を組み合わせる、分割と征服のアプローチかもしれないと思います。私はおそらくこれを行う良い人間関係があると思いますが、私は残念なことに参照がありません。
これはトピックであっても（プログラミング問題ではなく難しい数学問題です）、意味のある答えを得るために入力グラフの分布を指定する必要があります。 –
私が必要とするのは、n頂点を持つグラフを得て、それが1クロマティック、2クロマチック、またはこれに類似する確率を知ることです。これはあなたが探している入力グラフの分布ですか？ –
ポールがどのような入力グラフの分布を参照しているのか、また有彩数に関する事実がより役立つかもしれないという詳細については、私の答えを見てください。 –