What information entered the process?
Labs / Computer Science
Graph Coloring
Pick a color and click the nodes to paint them. The one rule: no edge may join two nodes of the same color — break it and that edge flashes. Try to finish using as few colors as possible, then let the greedy auto-colorer take a turn.
Labs / Computer Science / Graph Coloring
Graph Coloring
Pick a color and click the nodes to paint them. The one rule: no edge may join two nodes of the same color — break it and that edge flashes. Try to finish using as few colors as possible, then let the greedy auto-colorer take a turn.
Why it matters
Why explore this?
Computer science turns clear rules into reliable processes. This model lets you step through those rules and see how each decision changes the result.
Explore
Try the model
colors 0conflicts 0χ hint 4valid no
Investigate
Questions to test
Predict first, try it in the model, then use what you observe to answer.
What to try
- What is the fewest colors you can finish with? Does the “χ hint” agree?
- Randomize the graph a few times — do graphs with more edges always need more colors?
- Add an edge between two nodes that already share a color. Which edge starts flashing, and why?
- Does the greedy auto-colorer always hit the true chromatic number, or can it waste a color?
- Can you draw a triangle of three mutually connected nodes and color it with only two colors?
Explain
Make sense of what happened
Trace the process one step at a time. Name the rule used at each important step, then explain why the final result follows from those rules.
Check
Before you leave
Which rule changed it?
Why did the process produce this result?
If you can answer all three using evidence from the model, you understand the main idea. If not, return to Explore and change one setting at a time.