Кіріспе

(Дұрыс) төбелерді түске бояу

Графтар теориясында, төбелердің тең өлшемді (өзара байланыссыз) ішкі жиындарға бөлінуіне қатысты күшті түске бояу – әр түстің әр бөлігінде дәл бір рет кездесетін (дұрыс) төбелерді түске бояу. Егер граф, төбелерді k өлшемді жиындарға кез келген бөлінісі үшін, күшті түске бояуға мүмкіндік берсе, онда граф күшті k түсті деп аталады. Егер G графының реті k-ға бөлінбейтін болса, жаңа графтың реті k-ға бөлінетіндей етіп, G-ға жеткілікті мөлшерде оқшауланған төбелер қосылады. Мұндай жағдайда, бұрын қосылған оқшауланған төбелерді ескермей, күшті түске бояу G графының күшті түске бояуы деп саналады.

Графтың G күшті хроматикалық саны sχ(G) – G күшті k түсті болатындай ең кіші k саны. Егер графтың күшті хроматикалық саны k болса, онда граф күшті k-хроматикалық деп аталады.

sχ(G) қасиеттерінің кейбіреулері:
sχ(G) > Δ(G). sχ(G) ≤ 3 Δ(G) − 1. Асимптотикалық жағдайда sχ(G) ≤ 11 Δ(G) / 4 + o(Δ(G)). Мұнда Δ(G) – максималды дәреже. Күшті хроматикалық сан Алон (1988) және Феллоуз (1990) есімді ғалымдардың тәуелсіз зерттеулерінің нәтижесінде енгізілді.

Қатысушы мәселелер

График пен төбелердің бөлінісі берілгенде, тәуелсіз көлденең U – бұл өзара көршілес емес төбелер жиыны, мұнда әр бөлікте U-дың дәл бір төбесі болады. Күшті түстің мағынасы – төбелерді өзара байланыспаған тәуелсіз көлденеңдерге бөлу (әр тәуелсіз көлденең бір "түс" құрайды). Бұл, графты түстің түсімен бояудан өзгеше, онда графтың төбелері берілген сандағы тәуелсіз жиынтықтарға бөлінеді, бірақ бұл тәуелсіз жиынтықтардың көлденең болуы талап етілмейді. Бұл ұғымдардың арасындағы айырмашылықты түсіндіру үшін бірнеше кафедрасы бар факультетті қарастырайық, онда деканы факультет мүшелерінен тұратын комитет құруды қалайды. Бірақ кейбір профессорлар-оқытушылар арасында келіспеушіліктер бар, сондықтан олар бір комитетке мүше бола алмайды. Егер "келіспеушіліктер" қатынастары графтың қабырғаларымен көрсетілсе, онда: Тәуелсіз жиын – бұл келіспеушіліктері жоқ комитет. Тәуелсіз көлденең – бұл келіспеушіліктері жоқ және әр кафедрадан бір мүшеден тұратын комитет. Графты түстің түсімен бояу – бұл факультет мүшелерін ешқандай келіспеушіліктері жоқ комитеттерге бөлу. Күшті түстің мағынасы – бұл факультет мүшелерін ешқандай келіспеушіліктері жоқ және әр кафедрадан бір мүшеден тұратын комитеттерге бөлу. Сондықтан бұл мәселе кейде «бақытты декан» мәселесі деп аталады.