293 KB33 KB200820252016Furmańczyk, HannaKubale, Marekletnik:10številka:2str. 333-347COBISSID:17834585ISSN:1855-3966URN:URN:NBN:SI:doc-050QJIMQenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneacorona graphcubic graphequitable chromatic numberequitable graph coloringkronski grafkubični grafnepristransko barvanjenepristransko kromatsko številoNP-hardnessNP-težkopolinomski algoritempolynomial algorithmEquitable coloring of corona products of cubic graphs is harder than ordinary coloring|A graph is equitably $k$-colorable if its vertices can be partitioned into ?$k$? independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest ?$k$? for which such a coloring exists is known as the equitable chromatic number of ?$G$? and it is denoted by ?$\chi_=(G)$?. In this paper the problem of determinig ?$\chi_ =$? for coronas of cubic graphs is studied. Although the problem of ordinary coloring of coronas of cubic graphs is solvable in polynomial time, the problem of equitable coloring becomes NP-hard for these graphs. We provide polynomially solvable cases of coronas of cubic graphs and prove the NP-hardness in a general case. As a by-product we obtain a simple linear time algorithm for equitable coloring of such graphs which uses ?$\chi_=(G)$? or ?$\chi_=(G)+1$? colors. Our algorithm is best possible, unless P=NP. Consequently, cubical coronas seem to be the only known class of graphs for which equitable coloring is harder than ordinary coloringGraf 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 barvanjeTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije