A gráfelméletben a matematika egyik ága , a köbös gráf egy 3. fokú szabályos gráf . Más szavakkal, ez egy olyan gráf, amelyben minden csúcsnál pontosan három beeső él található.
A kézfogás lemma következménye, hogy minden köbös gráfnak páros számú csúcsa van.
Szerint a Brooks-tétel , a csúcsok egy kocka alakú grafikon lehet színezett három színnel (vagy kevesebb), hogy a két szomszédos pont nem azonos színű, kivéve abban az esetben, a tetraéderes grafikon .
A kétkockás gráf egy szabályos, két fokozatú, két fokozatú gráf , vagyis egy olyan köbös gráf, amelynek csúcsai csak két színnel színezhetők.
A teljes grafikon az egyetlen köbös grafikon, amely 4 színt igényel
A Frucht grafikon színezése 3 színnel
egy bicubic gráf, 2 szín elég
A Petersen-gráf széleinek, egy sziporkának, 4 színre van szüksége
Szerint a vizing-tétel , élek a harmadfokú gráf színű 3 vagy 4 szín nélkül két széle azonos színű lény incidens a két csúcsot. A sziporkák összefüggő köbös gráfok, amelyek nem szorulnak, és 4 színre van szükségük.
A Petersen-tétel kimondja, hogy minden kocka grafikon nélkül isthmus van teljes párosítás .
Más szavakkal, ha egy köbgrafikonon bármelyik él egy ciklushoz tartozik, akkor létezik olyan élek halmaza, amelyek minden csúcson esnek, és mindegyik csúcs csak az egyik élnek a vége.
Ezt a tételt, amely a gráfelmélet egyik legrégebbi, 1891 óta, ma Tutte tételének (in) alkalmazásaként tekintik .
Példa a tökéletes illesztésre egy nem köbös grafikonon
A piros élek tökéletesen összekapcsolják a Petersen-gráfot.
A tételt általánosítottuk: egy sejtés, amelyet Michael D. Plummer és Lovász László fogalmazott meg, azt mondja, hogy minden isthmus nélküli köbgrafikonnak exponenciális számú tökéletes kapcsolata van . Ezt a sejtést Esperet, Kardoš, King és Kráľ demonstrálta 2011-ben.
A Hamilton-gráf , mehetünk végig a csúcsot csak egyszer.
A legtöbb köbgrafikon hamiltoniánus, de nem minden: annak valószínűsége, hogy hamiltoni lesz, 1-re hajlik, ha a csúcsok száma korlátlanul növekszik.
A köbgrafikonok akár sokoldalúak , köbösek és nem Hamilton- féleek is lehetnek egyszerre , ahogy Tutte grafikonja mutatja . Ezek lehetnek kétkocka alakúak és nem Hamilton-i is, amint azt a Horton-grafikon vagy az Ellingham-Horton 54-grafikon mutatja . A még mindig be nem bizonyított és érvénytelenített Barnette (in) sejtés azt mondja, hogy minden gráf mind kétkocka sokszögű, mind Hamilton-féle.
Ha egy köbös gráf Hamilton-féle, az LCF jelölése lehetővé teszi, hogy tömören ábrázolják.
Hamiltoni ciklus a dodekaéder grafikonon
A Bidiakis-kocka , ábrázolva annak kiemelésére, hogy sokszögű
A Bidiakis-kocka másképp rendezve: a kör kiemel egy Hamilton-ciklust