224 KB8 KB200820252015Lužar, BorutŠkrekovski, Risteštevilka:2letnik:8str. 291-295COBISSID:17229401ISSN:1855-3966URN:URN:NBN:SI:doc-J84G2CVZenUniverza na Primorskem, Fakulteta za matematiko, naravoslovje in informacijske tehnologijeArs mathematica contemporaneainjective coloringinjektivno barvanjeplanar graphravninski grafiteorija grafovWegnerjeva hipotezaWegner's conjectureCounterexamples to a conjecture on injective colorings|An injective coloring of a graph is a vertex coloring where two vertices receive distinct colors if they have a common neighbor. Chen, Hahn, Raspaud, and Wang Some results on the injective chromatic number of graphs, J. Comb. Optim. 24 (2012), 299-318. conjectured that every planar graph with maximum degree ?$\Delta \ge 3$? admits an injective coloring with at most ?$\lceil 3\Delta / 2 \rceil$? colors. We present an infinite family of planar graphs showing that the conjecture is false for graphs with small or even maximum degree. We conclude this note with an alternative conjecture, which sheds some light on the well-known Wegner's conjecture for the mentioned degreesInjektivno barvanje grafov je barvanje vozlišč, pri katerem dve vozlišči prejmeta različni barvi, če imata skupnega soseda. Chen, Hahn, Raspaud in Wang so postavili hipotezo, da za vsak ravninski graf z maksimalno stopnjo ?$\Delta \ge 3$? obstaja injektivno barvanje s kvečjemu ?$\lceil 3\Delta/2 \rceil$? barvami. Predstavimo neskončno družino ravninskih grafov z majhno ali sodo maksimalno stopnjo, za katere hipoteza ne drži. Članek zaključimo z alternativno domnevo, ki rahlo spominja na Wegnerjevo conjecture za omenjene stopnjeTEXTznanstveno časopisjejournalsSlovenian National E-content AggregatorNational and University Library of SloveniaUniverza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije