Chromatic number of Johnson Graphs
What is the chromatic number of J(n,3)?
J(7,3,2) has v = 35, k = 12, alpha = 7, omega = 5, chi = 6
J(8,3,2) has v = 56, k = 15, alpha = 8, omega = 6, chi = 7
J(9,3,2) has v = 84, k = 18, alpha = 12, omega = 7, chi = 7
J(10,3,2) has v = 120, k = 21, alpha = 13, omega = 8, chi = 10
J(11,3,2) has v = 165, k = 24, alpha = 17?, omega = 9, chi = 11
..
J(n,3,2) has v = C(n,3), k = 3(n-3), alpha = ??, omega = n-2 (EKR), chi as below
According to Etzion and Bitan, for n>7 the chromatic number depends on n mod 6 as follows:
- n mod 6 = 0 yields chi = n-1
- n mod 6 = 1 yields chi = n-2 (large set of STS)
- n mod 6 = 2 yields chi = n-1
- n mod 6 = 3 yields chi = n-2 (large set of STS)
- n mod 6 = 4 yields chi = n
- n mod 6 = 5 yields chi = n-1 (conjectured by Etzion, proved by Lijun Ji)