Үйлесімді бояу - Harmonious coloring

12 түсті қолдана отырып, 3 деңгейлі толық 7-ағаштың үйлесімді бояуы. Осы графиканың үйлесімді хроматикалық саны 12. кез келген аз түстер бірнеше жұп шыңдарда түстер жұбының пайда болуына әкеледі. Сонымен қатар, Митчемнің формуласы бойынша, χ_H(Т._7,3) = ⌈(3/2)(7+1)⌉ = 12.

Жылы графтар теориясы, а үйлесімді бояу Бұл (дұрыс) шыңдарды бояу онда түстердің әр жұбы ең көп дегенде бір шектес шыңдарда пайда болады. The үйлесімді хроматикалық сан χ_H(G) графиктің G - бұл кез-келген үйлесімді бояуға қажет түстердің минималды саны G.

Кез-келген графиканың үйлесімді бояуы бар, өйткені әр шыңға нақты түс беру жеткілікті; осылайша χ_H(G≤ | V (G). Графиктер бар G χ көмегімен_H(G)> χ (G) (мұндағы χ - хроматикалық сан ); бір мысал - ұзындығы кез келген> 2, ол 2 түсті болуы мүмкін, бірақ 2 түспен үйлесімді бояуы жоқ.

Χ кейбір қасиеттері_H(G):

${ displaystyle chi _ {H} (T_ {k, 3}) = left lceil { frac {3 (k + 1)} {2}} right rceil}$ , мұндағы Т._к,3 толық болып табылады $к$ -ары 3 деңгейлі ағаш. (Митчем 1989)

Үйлесімді бояуды алғаш рет Харари мен Плантхолт ұсынған (1982), бірақ бұл туралы өте аз мәлімет бар.

Сондай-ақ қараңыз

Сыртқы сілтемелер

Үйлесімді бояулар мен акроматикалық санның библиографиясы Кит Эдвардс

Әдебиеттер тізімі

Фрэнк, О .; Харари, Ф .; Планхолт, М. (1982). «Графиктің сызықтық-хроматикалық саны». Ars комбинациясы. 14: 241–252.
Дженсен, Томми Р .; Toft, Bjarne (1995). Графикті бояуға қатысты мәселелер. Нью-Йорк: Вили-Интерсиснис. ISBN 0-471-02865-7.
Митчем, Дж. (1989). «Графиканың үйлесімді хроматикалық саны туралы». Дискретті математика. 74: 151–157. дои:10.1016 / 0012-365X (89) 90207-0.