322 KB32 KB200820252016Atanasov, RistoPetruševski, MirkoŠkrekovski, Risteletnik:10številka:2str. 359-370ISSN:1855-3966COBISSID:2048381971URN:URN:NBN:SI:doc-01M0OWYVenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporanealihi kromatični indeksliho barvanje povezavliho pokritje povezavodd chromatic indexodd edge-coloringodd edge-coveringsubcubic graphsubkubičen grafT-joinT-spojOdd edge-colorability of subcubic graphs|An edge-coloring of a graph ?$G$? is said to be odd if for each vertex ?$v$? of ?$G$? and each color ?$c$?, the vertex ?$v$? either uses the color ?$c$? an odd number of times or does not use it at all. The minimum number of colors needed for an odd edge-coloring of ?$G$? is the odd chromatic index ?$\chi_o^{\prime}(G)$?. These notions were introduced by L. Pyber L. Pyber, Covering the edges of a graph by . . ., in: Sets, graphs and numbers (Budapest, 1991), North-Holland, Amsterdam, volume 60 of Colloq. Math. Soc. János Bolyai, pp. 583-610, 1992, who showed that 4 colors suffice for an odd edge-coloring of any simple graph. In this paper, we consider loopless subcubic graphs, and give a complete characterization in terms of the value of their odd chromatic indexBarvanje povezav grafa ?$G$? se imenuuje liho, če je za vsako vozlišče v grafa ?$G$? in za vsako barvo ?$c$?, vozlišče v bodisi incidentno liho mnogo povezavam z barvo ?$c$? bodisi nobeni povezavi z barvo ?$c$?. Minimalno število barv, potrebnih za liho barvanje povezav grafa ?$G$? je lihi kromatični indeks ?$\chi_o^{\prime}(G)$?. Te pojme je vpeljal Pyber, ki je pokazal, da 4 barve zadoščajo za liho barvanje povezav vsakega enostavnega grafa. V članku, obravnavamo subkubične grafe brez zank, in podamo popolno karakterizacijo v smislu vrednosti njihovega lihega kromatskega indeksaTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije