4 - 2024 ACF Regionals @ Nebraska

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

Back to bonuses

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


Texas A	Claremont A	10	10
Iowa B	Iowa A	10	10
UBC A	Texas A&M A	10	10
Michigan State A	Texas A&M B	10	10
UW A	Rice A	10	10
Sorbonne	Appalachian State	10	10