graph coloring game
Let an agent explain the graph colouring game and its variants, define the game chromatic number and related parameters, relay known results and bounds with attribution, and separate the game from ordinary graph colouring and from map colouring puzzles.
Bundle → Layer → Finding → Questions Filled
4 bundles · 8 layers · 8 findings · 16 questions
Rules How the game works.
Play
Rules.
Play
Play.
- What are the rules, who wins, and how do variants differ? definition
- Is the question about the game or about ordinary graph colouring? boundary
Parameter
Game chromatic number.
Parameter
Parameter.
- How is the game chromatic number defined, and how does it relate to the chromatic number? definition
- Which entry fits the chromatic number? action
Results Known results.
Bounds
Bounds by class.
Bounds
Bounds.
- What bounds are known for trees, planar graphs and other classes, with attribution? provenance
- Which references are standard? provenance
Open
Open problems.
Open
Open.
- Which problems remain open? provenance
- What is proven versus conjectured? boundary
Strategy Strategies and computation.
Strategies
Winning strategies.
Strategies
Strategies.
- What strategies, such as activation strategies, give the bounds? provenance
- Which entry fits combinatorial game theory? action
Computation
Computing outcomes.
Computation
Computation.
- How are outcomes computed for small graphs, and what is the complexity? measurement
- Which entry fits computational complexity? action
Context History and teaching.
History
Origins.
History
History.
- How did the game originate, from Brams and Gardner to the research literature? provenance
- Which entry fits recreational mathematics? action
Teach
Teaching.
Teach
Teaching.
- How is the game used in teaching graph theory? action
- Which misconceptions arise? provenance
Classifiers Filled
- Family
- Thing Registry
- Category
- Cross-cutting context
- Entry kind
- thing
- Plane
- XCT
- Domain
- XCT.REL
- Other names and narrower kinds
- map-coloring games
What it is Filled
A two-player game on a graph in which players alternately colour uncoloured vertices from a fixed set of colours so that adjacent vertices differ, one player trying to complete a proper colouring and the other trying to block it; the game chromatic number is the least number of colours with which the first player can always win, and the game is studied in combinatorial game theory and graph theory.
Why it exists Filled
Let an agent explain the graph colouring game and its variants, define the game chromatic number and related parameters, relay known results and bounds with attribution, and separate the game from ordinary graph colouring and from map colouring puzzles.
Distinguishing features Filled
- Adversarial version of graph colouring
- Game chromatic number as the key parameter
- Results depend on who moves first and on passing rules
- Studied for planar graphs, trees and other classes
What robots and AI may and may not do Filled
Must not
- Present open problems on game chromatic numbers as solved.
- Confuse the game chromatic number with the ordinary chromatic number.
- Attribute results to researchers who did not obtain them.
Only with a human decision
- Correcting a published bound.
May
- Explain the rules of the graph colouring game and the game chromatic number.
- Play, analyse or teach the game.
Moral aspects Filled
- Accurate attribution matters in research.
- Clear explanations make mathematics accessible to learners.
Who is affected
- Students
- Researchers
Owners Filled
Steward
Nobody owns the concept; it belongs to mathematics.
Links to other meta-models Filled
parent
- Q11371326 - registry parent class
related
- finite two-player zero-sum game - game classification
- graph colouring - the underlying problem
- game chromatic number - its main parameter
- combinatorial game theory - the field
What else AI and robots need to interact with it Filled
Identity and identifiers required Filled
- Vercy registry: vr.tr.graph-coloring-game
- Wikidata: Q18207514 (https://www.wikidata.org/wiki/Q18207514)
Direct properties not applicable Not applicable
Not applicable
Plane XCT: no invented physical properties.
Recognition optional Filled
- Alternating colouring of vertices by two players
- One player aims for a proper colouring, the other to block
- Ordinary graph colouring has no adversary
- Not visible; a game played on a diagram of vertices and edges.
Capabilities and actions required Filled
- explain the rules and variants
- define the game chromatic number
- relay known bounds for graph classes
- distinguish it from ordinary colouring
Hazards and failure modes required Filled
- Confusing game chromatic number with chromatic number
- Mixing variants with different rules
- Citing bounds without their graph class
Standards and interfaces required Filled
- No regulation; definitions follow the research literature
Context of use required Filled
- Not for anything; an object of study in graph theory.
- vertex colouring game
- edge colouring game
- map colouring games
- variants with passing or with the blocker moving first
- game chromatic number and game colouring number
Sources Filled
- Wikidata item Q18207514: graph coloring game - identity and sense of the item
- Wikipedia: Graph coloring game - general description of the item
Open questions
- Should the game chromatic number be a separate entry?
- How should research surveys be linked?
- Which open problems, such as the exact value for planar graphs, should be recorded?
Machine files
Provenance
thing registry research (pass 2) · unreviewed
Built from: models/things/publications/thing-q18207514/spec.json