Math 2.0

Combinatorics Theorem

On-line colouring of forests needs few vertices

Builds on Graph colouringForest

Statement

Two players build a graph in rounds. In each round, Builder adds one new vertex and joins it to any chosen set of earlier vertices. Then Assigner at once gives the new vertex a colour that differs from the colours of all its neighbours. A colour is never changed later, and Assigner sees only the part of the graph built so far. This is an on-line colouring.

Let nn be a positive integer. Then Builder has a strategy such that the final graph is a forest with at most 2n−12^{n-1} vertices, and Assigner is forced to use nn distinct colours, whatever Assigner does.

Remarks

A forest is bipartite, so it has an off-line colouring with 22 colours. The theorem shows that an on-line Assigner can be forced to use arbitrarily many colours even on forests.

Reading path

To understand this page from the ground up, read these 12 pages in order. The foundations come first.

Show the path as a graph
Graph, definition, no evidence levelGraphdefinitionGraph colouring, definition, no evidence levelGraph colouringdefinitionWalk, definition, no evidence levelWalkdefinitionReachability, definition, no evidence levelReachabilitydefinitionTrail, definition, no evidence levelTraildefinitionConnected graph, definition, no evidence levelConnected graphdefinitionCircuit, definition, no evidence levelCircuitdefinitionCycle, definition, no evidence levelCycledefinitionAcyclic graph, definition, no evidence levelAcyclic graphdefinitionTree, definition, no evidence levelTreedefinitionForest, definition, no evidence levelForestdefinitionOn-line colouring of forests needs few vertices, statement, no evidence levelOn-line colouring of …statement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Graph definition
  2. Graph colouring definition
  3. Walk definition
  4. Reachability definition
  5. Trail definition
  6. Connected graph definition
  7. Circuit definition
  8. Cycle definition
  9. Acyclic graph definition
  10. Tree definition
  11. Forest definition
  12. On-line colouring of forests needs few vertices statement

Further reading

  1. Web https://github.com/mitchkeller/applied-combinatorics/blob/ebd95d6bd59e23c633c65cf560bcb93efa912aae/source/s_kitchensink_online.ptx#L24, source/s_kitchensink_online.ptx:24
About this page
TagF19XGQZKCG
URIm2://F19XGQZKCG
Kindstatement, theorem
WritingW1 stated
MSC05C15, 05C05, 68W27
StatusThis copy of the site has no build data. Run m2 status F19XGQZKCG.
AboutGraph colouring
UsesGraph colouring, Forest
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W2

  • edge proves in: at least one proof node (0 of 1)
  • edge instance_of or illustrates in: one example that shows the statement at work (0 of 1)
  • explanation L2 (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.