yokobuttonの不定期で競技プログラミングをするブログ

不定期で解けた競技プログラミングコンテストの問題を載せています。

2021-05-06から1日間の記事一覧

リスト彩色とリスト彩色予想②

2,リスト彩色予想 リスト彩色予想 任意の単純グラフGは、ch1(G)=χ1(G)である。 (証明) 1つ反例を示すことで、予想を否定する。 完全グラフKpの位数が奇数の場合を考える。Kpのサイズqはp(p-1)/2である。 完全グラフKpに対してχ1(Kp)=p(pが奇数)、p-1(pが偶…

リスト彩色とリスト彩色予想①

(注意)この記事はディーステル「グラフ理論」の内容をお借りしている部分が多いです。 1、リスト彩色 グラフGと、その各頂点に対して塗ることが許される色のリストが与えられている。このとき、そのリストから選んだ色を頂点に割り当てて、Gを彩色すること…

17人で3つの話題

漫画「数学ゴールデン」の1巻に次のような問題が出てくる。それを解いてみた。 「17人それぞれが他の全員と互いに手紙のやりとりをしている。 その手紙では3つの話題のみがやりとりされている。 そして、同じ2人組の間でなされる話題は常に同じ1つのやりとり…