graph coloring
Let an agent explain graph colouring, relay definitions, theorems, complexity and applications from mathematics and computer science sources, describe the named variants and flag the dicut alias, and distinguish graph colouring from map colouring as a special case, graph labelling in general and colour theory.
Research draft, second pass
A second pass drafted this model: the structure a model of this thing needs, and what is known about it in the world. The line under this one says how the second half was obtained - researched against sources, or recalled without web access, in which case nothing here was read anywhere and every claim is a lead to verify. Unreviewed either way.
written by Claude from model knowledge without web access - no source was read, every claim is a lead to verify
Researched by: Claude
Purpose and description
Let an agent explain graph colouring, relay definitions, theorems, complexity and applications from mathematics and computer science sources, describe the named variants and flag the dicut alias, and distinguish graph colouring from map colouring as a special case, graph labelling in general and colour theory.
In graph theory, the assignment of labels called colours to elements of a graph subject to constraints, most commonly vertex colouring, where adjacent vertices receive different colours and the minimum number needed is the chromatic number, and edge colouring, where adjacent edges differ, bounded by Vizing s theorem of 1964, along with variants such as list colouring, list edge colouring and centred colouring; deciding whether a graph can be coloured with three or more colours is NP-complete, the four colour theorem for planar maps was proved with computer assistance by Appel and Haken in 1976, and applications include scheduling, register allocation and frequency assignment. The registry alias dicut names a directed cut, a different concept.
What it is for: Solving constraint problems modelled on graphs.
It can be explain definitions and theorems; relay complexity; describe named variants; relay applications.
Distinguishing features
Adjacency constraints
Chromatic number
Computational hardness
Many variants
What it looks like
Not a visible object; drawn as graphs with coloured vertices or edges.
Physical character
four colour theorem proof: 1976 year - Appel and Haken
Vizing s theorem: 1964 year - edge chromatic number is max degree or plus one
3-colourability: NP-complete note
How it is recognised
Assigning colours to graph elements under constraints
Edge colouring, list colouring, dicut, vertex colouring, centred colouring, list edge-colouring
Map colouring is planar graph colouring; graph labelling is broader; colour theory concerns perception and art
Related models
is a kind of - in registry terms
includes -
is related to -
is contrasted with - misfiled alias
In practice
Families and kinds
vertex colouring
edge colouring
list colouring
total colouring
centred and other structural colourings
Standards and regulation
No regulation
Failure modes and hazards
Confusing greedy heuristics with optimal colourings
Misfiled dicut alias
Overstating the four colour theorem to non-planar maps
Also called
Where this came from
wikidata · CC0 1.0
Drafted structure
Bundle to layer to finding to question, as the second pass will find it: 4 bundles · 8 layers · 8 findings · 16 questions.
Understand What graph colouring is.
Science.
Definition
Definition.
Definition
Definition.
- What is graph colouring, and how does it differ from map colouring, graph labelling and colour theory? definition
- Is the question about theory, algorithms, scheduling or puzzles? boundary
Variants
Named variants.
Variants
Variants.
- What are vertex, edge, list, list edge and centred colouring, and why is a dicut different? definition
- Which entry fits the specific variant? action
Theory Theorems.
Science.
Four colours
Four colour theorem.
Four colours
Four colours.
- What does the four colour theorem state, and why was its computer proof controversial? provenance
- Which references are standard? provenance
Bounds
Bounds and theorems.
Bounds
Bounds.
- What do Brooks and Vizing theorems say about chromatic numbers? provenance
- Which sources are cited? provenance
Computing Algorithms.
Application.
Complexity
Complexity.
Complexity
Complexity.
- Why is graph colouring NP-complete, and what heuristics are used? provenance
- Which entry fits NP-completeness? action
Applications
Applications.
Applications
Applications.
- How is colouring used in timetabling, register allocation and frequency assignment? provenance
- Which entry fits register allocation? action
Context Puzzles and history.
Context.
Sudoku
Puzzles.
Sudoku
Sudoku.
- How can Sudoku be viewed as a graph colouring problem? provenance
- Which entry fits Sudoku? action
History
History.
History
History.
- How did Francis Guthrie s 1852 question start the four colour problem? provenance
- Which entry fits Francis Guthrie? action
What the second pass must settle
- The registry alias Dicut should be moved to directed cut
- How should mathematics sources be linked?
- Should list colouring be a separate entry?