Question
The chromatic polynomial counts a graph’s proper colorings, that is, the number of ways to assign colors to vertices such that adjacent vertices are colored differently. For 10 points each:
[10e] The chromatic polynomial of a planar graph evaluated at this integer or greater is always positive, since any planar graph can be properly colored using only this many colors.
ANSWER: 4
[10h] To show that the chromatic polynomial is actually a polynomial in the number of colors, one can use induction and these two graph operations, both of which reduce the number of edges by one. Name both operations.
ANSWER: edge deletion AND contraction [prompt on constructing graph minors]
[10m] The chromatic polynomial on this kind of graph is a falling factorial of the number of colors, since all vertices must be properly colored differently. The simplest non-planar graph by number of vertices is this kind of graph.
ANSWER: complete graphs
<Other Science>
Summary
| 2024 ACF Regionals @ Berkeley | 01/27/2024 | Y | 3 | 16.67 | 100% | 67% | 0% |
| 2024 ACF Regionals @ JMU | 01/27/2024 | Y | 8 | 12.50 | 88% | 25% | 13% |
| 2024 ACF Regionals @ Minnesota | 01/27/2024 | Y | 2 | 20.00 | 100% | 50% | 50% |
| 2024 ACF Regionals @ Nebraska | 01/27/2024 | Y | 6 | 10.00 | 100% | 0% | 0% |
| 2024 ACF Regionals @ Ohio State | 01/27/2024 | Y | 3 | 10.00 | 67% | 33% | 0% |
| 2024 ACF Regionals @ Rutgers | 01/27/2024 | Y | 5 | 20.00 | 100% | 80% | 20% |
| 2024 ACF Regionals @ Imperial | 01/27/2024 | Y | 8 | 12.50 | 100% | 25% | 0% |
| 2024 ACF Regionals @ Vanderbilt | 01/27/2024 | Y | 5 | 10.00 | 100% | 0% | 0% |
Data
| Minnesota B | Arizona State | 10 | 0 | 0 | 10 |
| Iowa State | Minnesota C | 10 | 10 | 10 | 30 |