Čtyřúhelníkové stěny
Úloha číslo: 3277
Nalezněte graf, který lze nakreslit na torus tak, že má všechny stěny ohraničeny čtyřcyklem a přitom má barevnost tři.
Nápověda
Graf může mít lichý cyklus jako podgraf, aniž by to byla jeho stěna.
Řešení
Například toroidální mřížka \(3\times 3\) obsahuje trojúhelník, a přitom ji lze obarvit třemi barvami, viz obrázek.
Varianta
Zkuste najít graf se stejnými podmínkami na nakreslení, ale aby měl barevnost čtyři.
Nápověda
Zkuste opět vyjít z mřížky, ale tentokrát ji na torus naviňte ‘našikmo’.
Pro popis takového grafu je možné využít algebraické nástroje, konkrétně Cayleyho grafy. Cayleyho graf pro grupu \(G\) a množinu generátorů \(X \subseteq G\) je graf na \(|G|\) vrcholech \(V\), kde každý vrchol odpovídá jednomu prvku grupy \(G\) a hrany odpovídají složením s generátory.
Jinými slovy, existuje bijekce \(f: V \rightarrow G\) taková, že vrcholy \(u,v\) jsou spojené hranou, právě když existuje \(x \in X\), že \(f(u) x = f(v)\) nebo \(f(u) x ^{-1}= f(v)\). Cayleyho graf se obvykle označuje \(Cay(G,X)\).
Příklady: \(C_5 = Cay(\mathbb Z_5, \{1\})\), \(K_5 = Cay(\mathbb Z_5, \{1{,}2\})\).
Řešení
Vezměme Cayleyho graf \(G = Cay(\mathbb Z_{13}, \{1{,}5\})\). Tento graf lze nakrestlit na torus se čtyřúhelníkovými stěnami.
Obsahuje lichý cyklus 0-12, tedy jeho barevnost je alespoň 3.
Sporem ukážeme, že barevnost je alespoň 4. Kdyby šel \(G\) obarvit třemi barvami, bylo by některou z barev nutno použít alespoň pětkrát. Bez újmy na obecnosti, nechť je to červená a nechť je vechol 0 červený. Červenou pak nelze použít na jeho sousedech, a tedy ze zbylých osmi vrcholů musejí být čtyři červené. Na těchto vrcholech lze naléz osmicyklus 2-3-4-9-10-11-6-7, tedy buď jsou červené 2,4,10 a 6; nebo 3,9,11 a 7. První možnost je vyoučena kvůli hraně \((2{,}10)\) druhá kvůli \((3{,}11)\).
Obarvení čtyřmi barvami ovšem existuje, dokonce jednu z barev stačí použít jen jednou.
Varianta
Dokážete najít graf, který by měl barevnost čtyři a jehož nakreslení v projektivní rovině by mělo všechny stěny čtyřúhleníkové?
Řešení
Stačí šikovně nakreslit graf \(K_4\). Má tři stěny, na obrázku jsou vyznačeny barevně.