Č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.

    Torus, chromatic number 3
  • 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.

    Cayleyho graf

    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)\).

    Barvení Cayleyho grafu

    Obarvení čtyřmi barvami ovšem existuje, dokonce jednu z barev stačí použít jen jednou.

    Obarvení čtyřmi barvami
  • 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ě.

    K4 na projektivní rovině
Obtížnost: Obtížná úloha
Úloha řešená úvahou
Úloha vyžadující neobvyklý trik nebo nápad
En translation
	Zaslat komentář k úloze