Теория графов и комбинаторика

S T I . I . Хиоматичпокий индокс IT хтоматичноков чяоло Г'ОА'ТА Граф = нааывавг'оя реберно-раокрапшшгам, аоли его padpaM прнпиоанн цвэ'га' г ак , что никакие два GMe'i?.,.df рзбра но имеют одинаковог'' цвета. Если дая этого чопользуатоя !< кг-'оок, 'яо граф называется робарио-К-раокрашвнним. . Хроматичеоким инденоом графа & назыпаегоя 4I-IGJI(J Л (S), равпоа минимальному чиолу К , при котором являстоя ра- бдрно-К-раск|ишен1шм. Если К', то граф С наэцнаотоя P'^lepuo-K-хрошти .^оким., Если К , то множество ребор X моете разбить к а к поперосвкавщихся мяожаогв в каадоад и з которнх нет смежных ребер. Вое рэбра глюжботва X ; пмшт 1-й цвет. Множества иаэнвают'^я одпоцвегт-адч ь-ласа^ Mi!. Легко saMSTuTXi, что ка^дай из одной,аетш:. маооов т л я а т о я паросочатаниам в графе <? , Поэтому ) мош;о Л'ор- претировать как нанмзньшяа число ггарооочвтенйй, на которко раа- • биваатоя мнокаств'^ ребор X . Так как воо ребра, к'щидонтныо од­ ной вершине, дожам имВ'ГЬ разпио м е т а , то очевидна оценка: J^(6-} А (G) , (ИЛ) г д е A t f f ) = Лашо заметить, что дяя дву­ дольного графа X( G ) ДС (г), В общем случае X i.G-) А С& • Доказано, любой простой граф являзтоя рабарно- (лО?) + 0 - -раокрашиввЕк.шм, т . е . Х С & ) ^ А С 6 ) + 1 . • Но, аняломш о ребзркоМ хйокраокой расома'грнвав'гоя Bapiuisii- Ш)Я раскрас:са .графа. Граф навивается в0р1иш!о--К"раокрашивайшк, аоли 014) воршшш монно раокраоить К -краскаии так, чтобы ника- ; кие две омажние вершины не пмоли би одинаковый цвет. Нинимальноо : число k; , при котором граф f ' является вартинно-К-раокрашивае- I мнм. называется хроматичас-.им числом рра(ра и обоаиачавт'од I Граф ^ -газнвается К-хроматическим, а о л и ^ ( ^ ) = | < , Вер- ' щин15ую раокраоку называют нросго риокраокрй. Очевидно, К -i-iac- ^ крао^ J порождаат j збаэняе (лиоквотва вершин V на к. подмнокестЕ (одноцветных классов) V t ( . V iС V) , в каждом из классов Vl нет смежных вершин. Аналогично всякое раабиание V на ТВКЙЙ подмножества соответствует некоторой раокраоке. Приведем некото­ рые ОЦв0^"т ДО(ЯX ' S ' ) , 6 5