MathCastle
Graph TheorySuperchallengeGraph Coloring

Graph Coloring · Superchallenge problem

Let GG have as its vertices the (62)=15\binom{6}{2}=15 two-element subsets of {1,2,3,4,5,6}\{1,2,3,4,5,6\}, with two subsets adjacent exactly when they are DISJOINT. The largest family of PAIRWISE-INTERSECTING subsets (an independent set of GG) has size 55 (e.g. all 55 pairs containing the element 11), and for 66 elements this maximum is achieved ONLY by such "star" families (all pairs sharing one fixed common element). What is χ(G)\chi(G)?