Equitable coloring of corona products of cubic graphs is harder than ordinary coloring - Furmańczyk, Hanna (Ars mathematica contemporanea, 2016)
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 ?$χ_=(G)$?. V tem članku študiramo problem določitve ?$χ_ =$? 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 ?$χ_=(G)$? ali ?$χ_=(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.
Keywords: corona graph; cubic graph; equitable chromatic number; equitable graph coloring; kronski graf; kubični graf; nepristransko barvanje; nepristransko kromatsko število; NP-hardness; NP-težko; polinomski algoritem; polynomial algorithm