Bevezetés a számításelméletbe II.
4. gyakorlat 2002. március 7-8.
Csütörtök 10-12 IB-140 és péntek 8-10 IB-145
 
 
Gráfok színezése

 

1. Határozzuk meg az alábbi gráfok kromatikus számát és maximális klikkméretét!
   
2. Mennyi $\omega(G)$, ha $G$ egy páros gráf legalább egy éllel?
3. Milyen összefüggés írható fel az $\omega(\cdot)$ és az $\alpha(\cdot)$ függvények között?
4. A $G$ gráfra $V(G)=\{v_1,v_2,\dots,v_{81}\}$, továbbá a $v_i$ és $v_j$ pontok között pontosan akkor van él, ha $\frac{i}{j}=3^k$ valamely $k \neq 0$ egésszel. Mennyi $\chi(G)$?
5. Bizonyítsuk be a $\chi(G) \ge \vert V(G)\vert / \alpha(G)$ egyenlőtlenséget!
6. Igazoljuk, hogy $\chi(G) \le \tau(G) + 1$!
7. Mutassuk meg, hogy bármely $G$ gráf csúcsai sorbarendezhetők úgy, hogy a csúcsokat ebben a sorrendben mohó módon színezve $\chi(G)$ színű színezéshez jutunk.
8. A $G$ gráf fokszámainak sorozata $d_1 \ge d_2 \ge \dots \ge d_n$. Bizonyítsuk be, hogy
   $$\chi(G) \le \max_{i=1,\dots,n}\{\ \min\{d_i+1,i\} \ \}.$$

9. HF A $V(G)=\{1,2,\dots,1023\}$ ponthalmazon definiáljunk egy gráfot úgy, hogy két pont között akkor és csak akkor legyen él, ha a két szám közül az egyik osztja a másikat. Határozzuk meg $\chi(G)$ értékét!
10. HF Bizonyítsuk be, hogy $\chi(G) \chi(\bar{G}) \ge \vert V(G)\vert.$
11. HF Egy $n=2k$ pontú teljes gráfból elhagytuk egy Hamilton-kör éleit. Mennyi az így kapott gráf kormatikus száma? Mi a helyzet, ha $n=2k+1$ pontú teljes gráfból hagyjuk el az éleket?
12. HF Tetszőleges $k,l>0$ egészekre mutassunk példát olyan gráfra, ahol $\chi(G)=k$, $\alpha(G)=l$ és $\vert V(G)\vert=\chi(G) \alpha(G)$.
13. HF Adott a síkon néhány egyenes, melyek közül semelyik három nem metszi egymást egy közös pontban. Tekintsük az egyenesek metszéspontjait egy $G$ gráf pontjainak, és a gráf élei legyenek az egyes egyeneseken szomszédosan elhelyezkedő csúcspárok. Igazoljuk, hogy $\chi(G)\le 3$. (Segítség: valamilyen mohó színezést érdemes mutatni, csak arra kell rájönni, hogy milyen sorrendben érdemes a pontokat kiválasztani.)

$\alpha(G)$

Egy maximális független ponthalmaz mérete;

$\tau(G)$

Egy minimális lefogó ponthalmaz mérete;

$\nu(G)$

Egy maximális független élhalmaz mérete;

$\rho(G)$

Egy minimális lefogó élhalmaz mérete;

$\Delta(G)$

Maximális fokszám;

$\omega(G)$

Egy maximális méretű klikk pontjainak száma;

$\chi(G)$

Egy minimális számú színt használó színezésben felhasznált színek száma.