| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén a de Bruijn–Erdős-tétel, amit először Nicolaas Govert de Bruijn and Paul Erdős igazolt, azt állítja, hogy a kromatikus száma, amennyiben az véges, megegyezik a véges részgráfjainak kromatikus számai közül a legnagyobbal. A tétel szerint egy G végtelen gráf akkor és csak akkor k-színezhető (valamely véges k-ra úgy, hogy semelyik két szomszédos csúcs színe se egyezzen meg), ha minden véges részgráfja is k-színezhető. Ezzel ekvivalens állítás, hogy minden k-kritikus gráfnak (olyan gráfnak, aminek színezéséhez k színre van szükség, de minden részgráfjának ennél kevesebbre) véges számú csúccsal kell rendelkeznie. Bár a de Bruijn–Erdős-tételnek számos különböző bizonyítása létezik, mindegyik a kiválasztási axiómára alapul. A tétel alkalmazásai közé tartozik a négyszíntétel és a Dilworth-tétel kiterjesztése véges gráfokról és részbenrendezett halmazokról végtelenre, továbbá a sík kromatikus számával foglalkozó Hadwiger–Nelson-probléma redukálása véges gráfokra vonatkozó problémára. A tétel általánosítható véges számú színről olyan színhalmazokra, melynek számossága kardinális szám (wd). (hu)
- A matematika, azon belül a gráfelmélet területén a de Bruijn–Erdős-tétel, amit először Nicolaas Govert de Bruijn and Paul Erdős igazolt, azt állítja, hogy a kromatikus száma, amennyiben az véges, megegyezik a véges részgráfjainak kromatikus számai közül a legnagyobbal. A tétel szerint egy G végtelen gráf akkor és csak akkor k-színezhető (valamely véges k-ra úgy, hogy semelyik két szomszédos csúcs színe se egyezzen meg), ha minden véges részgráfja is k-színezhető. Ezzel ekvivalens állítás, hogy minden k-kritikus gráfnak (olyan gráfnak, aminek színezéséhez k színre van szükség, de minden részgráfjának ennél kevesebbre) véges számú csúccsal kell rendelkeznie. Bár a de Bruijn–Erdős-tételnek számos különböző bizonyítása létezik, mindegyik a kiválasztási axiómára alapul. A tétel alkalmazásai közé tartozik a négyszíntétel és a Dilworth-tétel kiterjesztése véges gráfokról és részbenrendezett halmazokról végtelenre, továbbá a sík kromatikus számával foglalkozó Hadwiger–Nelson-probléma redukálása véges gráfokra vonatkozó problémára. A tétel általánosítható véges számú színről olyan színhalmazokra, melynek számossága kardinális szám (wd). (hu)
|
