Odd edge coloring of graphs

angleški

2015

letnik 9, številka 2

barvanje povezav   grafi   lihi podgraf   povezavna dekompozicija

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

Barvanje povezav grafa ?$G$? je liho barvanje povezav, če za vsako vozlišče ?$v$? grafa ?$G$? in za vsako barvo ?$c$?, vozlišče ?$v$? uporabi barvo ?$c$? lihokrat ali pa je sploh ne uporabi. V L. Pyber, Covering the edges of a graph by..., Graphs and Numbers, Colloq. Math. Soc. János Bolyai 60 (1991), 583-610. je Pyber dokazal, da 4 barve zadoščajo za liho povezavno barvanje vsakega enostavnega grafa. Nedavno so bili nekateri rezultati o tem tipu barvanj (multi)grafov uspešno uporabljeni pri reševanju problema parnosti lic povezavnega barvanja B. Lužar and R. Škrekovski, Improved bound on facial parity edge coloring, Discrete Math. 313 (2013), 2218-2222 in J. Czap, S. Jendrol', F. Kardoš and R. Soták, Facial parity edge colouring of plane pseudographs, Disc. Math. 312 (2012), 2735-2740. V tem članku predstavimo dodatne rezultate, in sicer dokažemo, da 6 barv zadošča za liho povezavno barvanje vsakega povezanega (multi)grafa brez zank, navedemo primere, ko je ta zgornja meja dosežena, in karakteriziramo družino povezanih (multi)grafov brez zank, pri katerih je meja 6 dosežena. Predstavimo tudi nekaj odprtih problemov.

29.05.2020