Grafové barvení

Výpisky kapitoly o Barvení z Modern Graph Theory.

Pro (vrcholovou) barevnost grafu $\chi(G)$ a hranovou barevnost grafu $\chi’(G)$ platí:

  • $\chi(G) \geq \omega(G)$ kde $\omega$ je klikovost grafu.
  • $\chi’(H) = \chi(L(H))$ kde $L(H)$ je line graf $H$.
  • $\chi(G) \geq |G|/\alpha(G)$ kde $\alpha$ je nezávislost.

Vrcholové barvení

Greedy algo barví hladově dle pořadí předložených vrcholů.

  • Obarví $K_{k,k} \setminus E_{k-1}$ pomocí nejhůře $k+1$ barev (E jsou isolované hrany).

  • Pro $k=max_H \delta(H)$, kde H je indukovaný podgraf G. Pak $\chi(G) \leq k+1$. DK: odeberme postupně vrcholy stupně max k, v obráceném pořadí zafunguje greedy algo.

  • Pro $H_0$ indukovaný podgraf $G$, pokud každý podgraf $H_0 \subset H \subset G, V(H_0) \neq V(H)$ obsahuje vrchol $x \in V(H) \setminus V(H_0)$ a $d_H(X) \leq k$, potom $$\chi(G) \leq \max{k+1, \chi(H_0)}.$$ – Mez k+1 vychází z greedy algo a $\chi(H_0)$ ofc lze upravit tak, aby se na $x$ napojovalo jinou barvou.

  • Pro graf G s max deg $\Delta$. Pokud G není cykl liché délky ani úplný graf, pak $\chi(G) \leq \Delta$. – Vyberme vrchol s max degree $\Delta$ a dva sousedy $x_1,x_2$, kteří nemají mezi sebou hranu. Pusťme DFS z $x_n$ na graf $G \setminus {x_1, x_2}$ a označujme projité vrcholy $x_{n-1}, x_{n-2}, \dots, x_3$. Všechny vrcholy mají v pořadí jeden vrchol neobarvený, a tak půjdou obarvit dobře jednou z $\Delta$ barev. Podslední vrchol sousedí s dovjicí x1 a x2, takže mu také zbude jedna barva.

Pozorujme nesousední vrcholy $x,y$ grafu $G$. Pokud mají v barvení jinou barvu, tak mezi ně lze dát hranu, vznikne graf $G’$. Pokud mají v barvení stejnou barvu, tak je můžeme spojit a vytvořit graf $G’’$. Tyto možnosti pokrývají všechny možnosti, proto platí $\chi(G)=\min{\chi(G’), \chi(G’’)}$ a $p_G(x)=p_{G’}(x)+p_{G’’}(x)$.

Označme $p_H(x)$ počet obarvení grafu $H$ pomocí $x$ barev.

Chromatic polynomial: Pro graf $H$ s $n \geq 1$ vrcholy, $m$ hranami a $k$ komponentami, pak $$p_h(x) = \sum_{i=0}^{n-k}(-1)^i a_i x^{n-i},$$ kde $a_0 = 1, a_1 = m$ a $a_i$ je pozitivní celé číslo pro všechna či, 0 \leq i \leq n-k$.

Hranové barvení

  • $\chi’(G) \geq \Delta(G)$
  • $\chi’(G) \geq \lceil e(G)/\beta \rceil$ kde $\beta$ je největší nezávislá množina hran.
  • Vizing – $\chi’(G) \in {\Delta, \Delta+1}$.

Barvení grafů na površích

  • Díky eulerově formuli máme odhad na počet hran $e \leq 3n-6$, takže jeden vrchol má vždy stupeň max 5, pak lze obarvit graph šesti barvami trháním těchto vrcholů nízkého stupně.
  • Každý planární graf lze obarvit pěti barvami. (DK si pamatuju)
  • Dolní mez pro barvení je hvězda napojená na lichý cykl, která potřebuje alespoň 4 barvy.

Eulerova charakteristika povrchu $\chi$ (name-clash s $\chi$ barevností)

  • $V-E+F-C = \chi$ a proto:
  • $e(G) \leq 3n - 3\chi$
  • Heawood bound – Chromatické číslo pro graf na uzavřeném povrchu s $\chi \leq 1$ je nejvíce $$h(\chi) = \left\lfloor \frac{7+\sqrt{49-24\chi}}{2} \right\rfloor.$$

List coloring

Každému vrcholu dejme množinu barev, kterými může být obarven. Mějme nejmenší k takové, že pokud mají všechny vrcholy množinu velikosti alespoň k a lze graf vždy obarvit, pak je list coloring $\chi_l(G) = k$.

Zřejmě $\chi_l(G) \geq \chi(G)$ ovšem jsou i případy kde $\chi_l(G) > \chi(G)$ (třeba bipartitiní grafy).

Alternativní důkaz 5-barevnosti planárních grafů pomocí list coloring (Thomassen’s theorem): Rozšiřme planární graf na skoro-triangulaci, tj. jedna stěna je cykl a zbylé jsou trojúhelníky. Předpokládejme, že všechny vrcholy cyklu mají list velikosti 3 a zbylé vrcholy velikosti 5. Pokud má cykl chordu, lze rozdělit na dva nezávislé menší případy. Pokud chordu nemá, tak vyberme vrchol x z cyklu. Vrchol x má v listu 3 barvy, vybereme jednu, kterou nemá ani předchůdce ani následník na cyklu. Z listu sousedů uvnitř triangulace dvě barvy odebereme (jedna zbude x) - zbývají jim 3 -> indukce.

Galvin’s theorem: $\chi’(G)=\chi_l’(G)=\Delta(G)$ for bipartite graphs.

It is conjectured that $\chi’(G)=\chi_l’(G)$ for every graph, however no luck so far.

Perfect graphs

A graph G is perfect if $\chi(H) = \omega(H)$ for every induced subgraph H of G.

All bipartite graphs are perfect.

A graph obtained from a perfect graph by replacing its vertices by perfect graphs is perfect.

The complement of a perfect graph is perfect.

Berge’s conjecture: A graph G is perfect if, and only if, neither G nor its complement G contains an induced odd cycle of length at least 5.

Random graphs

Stirling’s formula for factorial

  • $\sqrt{2\pi s} (s/e)^s \leq s! \leq e^{1/12s} \sqrt{2\pi s} (s/e)^s$

  • $(1-x) \leq e^{-x}$ and $(1-x)^k \leq e^{-kx}$ for all $x < 1, k \geq 0$.

Extremální grafy

Např. kolik musí graf obsahovat hran, aby byla zaručena podgrafu H?

  • Pro každé přirozené číslo n platí, že graf o n vrcholech, který neobsahuje trojúhelník, má nejvýše $T(n) = \lfloor \frac{n^2}{4} \rfloor$ hran.

Theorém (Erdös and Stone) Pro všechny celá čísla $r \geq 2, s \geq 1$, a všechna $\epsilon > 0$, existuje celé číslo $n_0$ takové, že každý graf s alespoň $n \geq n_0$ vrcholy a alespoň $$t_{r-1}(n) + \epsilon n^2$$ hranami obsahuje $K_s^r$ jako podgraf.

Corollary: Pro každý graf H s alespoň jednou hranou, $$\lim_{n \rightarrow \infty} \frac{\mbox{ex}(n, H)}{\binom{n}{2}} = \frac{\chi(H)-2}{\chi(H)-1}.$$

Gyárfás conjecture: pro každé $r \in \mathbb{N}$ a každý stom existuje celé číslo $k=k(T,r)$ takové, že každý graf s $\chi(G) \geq k$ a $\omega(G) < r$ obsahuje $T$ jako indukovaný podgraf.

Theorem: Existuje konstanta $c \in \mathbb{R}$ taková, že pro každé $r \in \mathbb{N}$, a každý graf s průměrným stupněm $d(G) \geq cr^2$ obsahuje $K^r$ jako topologický minor.

A graph H is called a topological minor of a graph G if a subdivision of H is isomorphic to a subgraph of G.

Theorem (Kostochka): Existuje reálná konstanta c taková, že pro každé $r \in \mathbb{N}$ a každý graf s průměrným stupněm $d(G) \geq cr\sqrt{\log r}$ obsahuje $K^r$ jako minor. Až na hodnotu konstanty je toto nejlepší možná mez určená jako funkce $r$.

Lemma: Mějme $d, k \in \mathbb{N}, d \geq 3$, a graf s minimálním stupněm $\delta(G) \geq d$ a obvodem $g(G) \geq 8k+3$. Pak $G$ má minor $H$ s minimálním stupněm $\delta(H) \geq d(d-1)^k$.