Equitable coloring of corona products of cubic graphs is harder than ordinary coloring

angleški

2016

letnik 10, številka 2

kronski graf   kubični graf   nepristransko barvanje   nepristransko kromatsko število   NP-težko   polinomski algoritem

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

Graf se imenuje nepristransko ?$k$?-obarvljiv, če lahko njegova vozlišča razvrstimo v ?$k$? neodvisnih množic na tak način, da se število vozlišč v poljubnih dveh množicah razlikuje za največ ena. Najmanjši ?$k$?, za katerega obstaja takšno barvanje, je znan kot nepristransko kromatsko število grafa ?$G$? in ga označimo ?$\chi_=(G)$?. V tem članku študiramo problem določitve ?$\chi_ =$? za krone kubičnih grafov. Čeprav je problem navadnega barvanja kron kubičnih grafov rešljiv v polinomskem času, je problem nepristranskega barvanja za te grafe NP-težak. Prikažemo polinomsko rešljive primere kron kubičnih grafov in dokažemo NP-težavnost v splošnem primeru. Kot stranski produkt dobimo preprost algoritem z linearno časovno zahtevnostjo za nepristransko barvanje takšnih grafov, ki uporabi ?$\chi_=(G)$? ali ?$\chi_=(G)+1$? barv. Naš algoritem je najboljši možen, razen če P=NP. Posledično, kubični kronski grafi se zdijo edini znani razred grafov, za katere je nepristransko barvanje težje kot običajno barvanje.

29.05.2020