Counterexamples to a conjecture on injective colorings - Lužar, Borut (Ars mathematica contemporanea, 2015)
Injektivno 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 ?$Δ \ge 3$? obstaja injektivno barvanje s kvečjemu ?$\lceil 3Δ/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 stopnje.
Keywords: injective coloring; injektivno barvanje; planar graph; ravninski grafi; teorija grafov; Wegnerjeva hipoteza; Wegner's conjecture