Cílem zápočťáku by bylo ověřit Cherlinův výsledek (viz
http://sites.math.rutgers.edu/~cherlin/Paper/census.pdf -- Appendix A).
Cherlin zde popsal všechny možné neizomorfní podmnožiny všech trojúhelníků
s hranami obarvenými čtyřmi barvami tak, aby třída úplných grafů, které
žádný z těchto trojúhelníků neobsahují jako indukovaný podgraf měla silnou
amalgamační vlastnost. Tím myslíme, že kdykoliv vezmeme dva úplné grafy z
této třídy a indukovaný podgraf takový, že je obsažen v obou těchto
grafech, pak můžeme tyto dva grafy přes tento podgraf slepit a doplnit
zbylé hrany tak, aby získaný graf znovu patřil do naší třídy.
Jednalo by se o bruteforce napsaný v C++ (který by byl ale celkem
implementačně náročný), potenciálně s různými heuristikami, který by měl
doběhnout v rozumném čase, a vypsat všechny hledané podmnožiny
trojúhelníků. Rád bych se následně pokusil o vyřešení problému i pro pět
barev -- nyní spíše nevěřím, že by se to dalo v rozumném čase stihnout, ale
je možné, že ověřování poběží v průměrném případě mnohem rychleji než v
případě nejhorším.