Brinkmannův graf - Brinkmann graph
| Brinkmannův graf | |
|---|---|
 Brinkmannův graf | |
| Pojmenoval podle | Gunnar Brinkmann |
| Vrcholy | 21 |
| Hrany | 42 |
| Poloměr | 3 |
| Průměr | 3 |
| Obvod | 5 |
| Automorfismy | 14 (D7 ) |
| Chromatické číslo | 4 |
| Chromatický index | 5 |
| Tloušťka knihy | 3 |
| Číslo fronty | 2 |
| Vlastnosti | Eulerian Hamiltonian |
| Tabulka grafů a parametrů | |
V matematický pole teorie grafů, Brinkmannův graf je 4-běžný graf s 21 vrcholy a 42 hranami objevenými Gunnarem Brinkmannem v roce 1992.[1][2] Poprvé byl publikován Brinkmannem a Meringerem v roce 1997.[3]
Má to chromatické číslo 4, chromatický index 5, poloměr 3, průměr 3 a obvod 5. Je to také 3graf spojený s vrcholem a 3-hranový graf. Je to nejmenší 4 pravidelný graf obvodu 5 s chromatickým číslem 4.[3] Má to tloušťka knihy 3 a číslo fronty 2.[4]
Podle Brooksova věta, každý k-pravidelný graf (kromě lichých cyklů a klik) má maximálně chromatické číslo k. Od roku 1959 bylo také známo, že pro každého k a l existují k-chromatické grafy s obvodem l.[5] V souvislosti s těmito dvěma výsledky a několika příklady včetně Chvátalův graf Branko Grünbaum v roce 1970 předpokládal, že pro každého k a l existují k-chromatický k-pravidelné grafy s obvodem l.[6] Chvátalův graf případ vyřeší k = l = 4 této domněnky a případ vyřeší Brinkmannův graf k = 4, l = 5. Grünbaumova domněnka byla vyvrácena pro dostatečně velkou k Johannsen, který ukázal, že chromatické číslo a graf bez trojúhelníků je O (Δ / log Δ), kde Δ je maximální stupeň vrcholu a zavádí se O velká O notace.[7] Navzdory tomuto vyvrácení však zůstává zajímavé najít příklady a je jich známo jen velmi málo.
The chromatický polynom Brinkmannova grafu je X21 - 42X20 + 861X19 - 11480X18 + 111881X17 - 848708X16 + 5207711X15 - 26500254X14 + 113675219X13 - 415278052X12 + 1299042255X11 - 3483798283X10 + 7987607279X9 - 15547364853X8 + 25384350310X7 - 34133692383X6 + 36783818141X5 - 30480167403X4 + 18168142566X3 - 6896700738X2 + 1242405972X (sekvence A159192 v OEIS ).
Algebraické vlastnosti
Brinkmannův graf není a vrchol-tranzitivní graf a jeho úplná skupina automorfismu je izomorfní s dihedrální skupina řádu 14, skupina symetrií a sedmiúhelník, včetně rotací i odrazů.
The charakteristický polynom Brinkmannova grafu je .
Galerie
The chromatické číslo Brinkmannova grafu je 4.
The chromatický index Brinkmannova grafu je 5.
Reference
- ^ Weisstein, Eric W. "Brinkmannův graf". MathWorld.
- ^ Brinkmann, G. „Generování kubických grafů rychlejší než kontrola izomorfismu.“ Předtisk 92-047 SFB 343. Bielefeld, Německo: University of Bielefeld, 1992.
- ^ A b Brinkmann, G. a Meringer, M. „Nejmenší 4-pravidelné 4-chromatické grafy s obvodem 5.“ Poznámky k teorii grafů New Yorku 32, 40-41, 1997.
- ^ Jessica Wolz, Inženýrské lineární rozložení se SAT. Diplomová práce, University of Tübingen, 2018
- ^ Erdős, Paul (1959), „Teorie grafů a pravděpodobnost“, Kanadský žurnál matematiky, 11 (0): 34–38, doi:10.4153 / CJM-1959-003-9.
- ^ Grünbaum, B. (1970), "Problém v barvení grafů", Americký matematický měsíčník, Mathematical Association of America, 77 (10): 1088–1092, doi:10.2307/2316101, JSTOR 2316101.
- ^ Reed, B. A. (1998), „ω, Δ a χ“, Journal of Graph Theory, 27 (4): 177–212, doi:10.1002 / (SICI) 1097-0118 (199804) 27: 4 <177 :: AID-JGT1> 3.0.CO; 2-K.