MathCastle
Graph TheoryHardGraph Coloring

Graph Coloring · Hard problem

Two pentagons share exactly one common vertex 00: the first is 0,1,2,3,40,1,2,3,4 (edges 01,12,23,34,4001,12,23,34,40) and the second is 0,5,6,7,80,5,6,7,8 (edges 05,56,67,78,8005,56,67,78,80) — 99 vertices, 1010 edges total, and no triangle anywhere. What is the chromatic number of this combined graph?