Dicotyledonous és bichromatic grafikonok
Definíció. Egy kromatográfiás χ (G) = 2 kromoszóma gráfnak kettõsnek kell lennie.
Tétel. A kétpárti ↔ G G gráfja egy bichromatic gráf.
Szükségesség →. legyen G = (V1, V2, E) kétpárti grafikon. A V1 csúcsai egy színben vannak színezve, a csúcsok a V2-től a másikig. A csúcsok eredő színezése helyes, mivel a szomszédos színes csúcsok, a V1 egyike és a másik a V2, különböző színűek. Következésképpen a grafikon bikromatikus.
← Teljesítmény. Legyen G egy bichromatic gráf, akkor a csúcsainak halmaza két osztályra osztható:
V1 - G-csúcsok, színes egy színben.
V2 a G színű, különböző színű csúcsok.
A G élei csak a különböző osztályokból álló csúcsokat tudják összekapcsolni, → a G = (V1, V2, E) gráf kétpólusú.
Megjegyzés. Az alábbi állítások egyenértékűek:
1) A G gráf bikromatikus.
2) A G gráf kétpólusú.
3) Minden G egyszerű ciklus egyenlő hosszúságú.
A fa egy bikromatikus grafikon, mivel a gráf egyenletes rétegeinek csúcsai színesek lehetnek egy színben, és a páratlan rétegek a másikban.
Jóváhagyása. Legyen Kp legyen egy teljes grafikon p-csúcsokkal, majd χ (Kp) = p.
Bizonyítás. Indukcióval p.
Alapja: p = 3 (háromszög), χ (K3) = 3.
Az indukció feltételezései: feltételezzük, hogy χ (Kp-1) = p-1 színek.
Lépés: Megmutatjuk, hogy χ (Kp) = p. Tény, hogy legyen néhány csúcs a Kp-ben. A csúcsot a Kp-ből eltávolítjuk a hozzá tartozó szélekkel együtt. Ezután a grafikon Kp - v = Kp-1 p-1 színű az indukciós hipotézissel p-1 színnel. 1,2,3 ... p-1. A Kp csúcsát csak az új festékkel lehet színezni. Ezért χ (Kp) = p. Az indukciós lépés be van állítva. Tétel: bizonyított.
Következmény. Van egy grafikon önkényesen nagy kromatikus számmal (teljes grafikonok).
Következmény. Van egy grafikon önkényesen kis kromatikus számmal (üres grafikonok).