299
правок
Изменения
→Случай произвольного графа
===Случай произвольного графа===
{{Теорема 1С.6. |statement=Для щствольного произвольного графа Н <tex>H</tex> существует рамсеевский граф,.|proof=Доказательство. Пусть к — <tex>k=v(H), п — гn=r(кk,кk)</tex>. Пронумеруем Еершины вершины графа Н<tex>H</tex>. Построим граф G0 <tex>G^0</tex> следующим образсмобразом: разместим его вершины е вершины в виде таблице п х Ск<tex>n \times C^k_n</tex>. Таким образом в каждом столбце Еершины вершины окажутся пронумерованы числами ст от 1 до п. <tex>n</tex>, как соответствующие строки строки таблицы. Е В каждом столбце одним из Ск <tex>C^k_n</tex> способов разместим граф Н <tex>H</tex> (каждый столбец соответствует одному из возможных споссбсЕ размещенияспособов размещения). Все рёбра графа G0 <tex>G^0</tex> будут рёбрами указанных копий графа Н, <tex>H</tex>. Граф G0 является п-дсльным, егс естественное разбиение на доли задаётся таблицей: V^(G°) — это вершины, соответствующие г ряду таблицы. Мы последовательно е несколько шагов будем нерестраивать наш граф с помощью леммы 1С.З так. чтобы вершины последующих графов также разбивались на п долей и записывались в виде таблицы. Каждый шаг будет состЕСтстЕСвать однсй паре строк таблицы,
Шаг перестройки графа.
Итак, пусть мы имеем n-дольный граф Ge, доли которого К = К(Сг) (где г 6 [1--п]) Пусть с парой строк (и. соответственно, долей) i,j мы еше не выполняли шаг. Очеьидно, граф Gitj = Gt{Vi\JVj) дЕудолен и для него не лемме 10.3 сушестЕует двудольный рамсееЕОкий граф Pitj. Еолее того если вершины Р^- разбиты на дес доли Wi и Wj. тс для любой раскраски рёбер в два цЕета существует одвснветнсе Есгружение (р графа Gitj е Pitj в котором (p(Vj) С Wi и ip(Vj) С Wj Назовём таксе погружение одноцветным.
Доказательство. Индукция с обратным ходом ст £ — С2п к £ — 0. База для £ = С\ очеЕидна. Докажем переход £ ^ £ — 1
Итак рассмотрим наш изоморфный G1 подграф который мы для простоты будем обозначать Ge и пару строку е нем пусть это строки г и j. a Pij и Gitj — те двудольные графы между этими строками, что списаны в шаге псстроения. Так как Pjj (подграф графа Ge) — рамссеЕСкий граф для Gij. мы межем выбрать одноцветное е раскраске р погружение Gij в Pitj и соответствующая ему по построению копия Ge_1 будет искомым (из построения очевидно, чте индуиирсьанным!) подграфом Ge а значит, bG □
Таким образом, сушестнует иземерфный G0 индуцированный подграф графа G. е кстсрем для каждой пары стрск i,j Есе ребра между Есршинами состЕСтстЕуюших строк одноцветны е раскраске р. Будем обозначать зтот граф просто G0. Бассмстрим граф Кп Еершины которого соответствуют строкам таблицы и искрасим каждое ребро в пест в который покрашены рёбра G0 между соответствующими строками Так как п = r(k,k) существуют к Есршин, между которыми ьсе рёбра одноцветны. Рассмотрим столбец графа G°, е котором Н размещён именно е строчках. соответствующих этим к вершинам. Подграф Н' графа G0 на вершинах этого столбца и соответствующих строчках из с мор фен Н пс построению является индугшрсЕанным подграфом графа G0 и все его рёбра одноцветны в раскраске р. Остаётся лишь заметить, что Я' — индуцированный подграф графа G. □}}
