{ "model": { "rank": 14617, "code": "thing-q504843", "model_id": "vr.tr.graph-coloring", "name": "graph coloring", "purpose": "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.", "family": "Thing Registry", "category": "Cross-cutting context", "status": "research-draft", "kind": "thing", "plane": "XCT", "domain": "XCT.QLT", "industry": "", "version": "", "url": "/models/thing/q504843/", "tier": 2, "score": 35, "payload": { "layer": "wikidata", "aliases": [ "edge coloring", "list coloring", "Dicut", "vertex coloring", "Centered coloring", "list edge-coloring", "subcoloring", "defective coloring", "fractional coloring", "harmonious coloring", "interval coloring", "weak coloring", "Tait coloring", "rainbow coloring", "incidence coloring", "conflict-free coloring", "packing coloring" ], "aliasCount": 17, "merged": 17, "knownIn": 35, "facets": null, "markers": [], "lexicalClass": "", "senseRank": null, "alsoRegisteredAs": null, "source": { "dataset": "wikidata", "item": "Q504843", "url": "https://www.wikidata.org/wiki/Q504843", "license": "CC0 1.0" } }, "research": { "vercy": "1.0-draft", "publication": { "status": "research-draft", "adjudicationStatus": "unreviewed", "publishableCanonical": false, "generatedAt": "2026-09-13T21:50:35Z", "providers": [ "Claude" ], "breadth": "written by Claude from model knowledge without web access - no source was read, every claim is a lead to verify", "pass": 2, "wave": 4, "engine": "claude" }, "metaModel": { "id": "THING-Q504843", "registryId": "vr.tr.graph-coloring", "name": "graph coloring", "version": "0.2.0-wave.4", "entryKind": "thing", "family": "Thing Registry", "domain": [ "XCT.QLT" ], "status": "research-draft" }, "canonicalUrl": "https://ver.cy/models/thing/q504843/", "model": { "registry_id": "vr.tr.graph-coloring", "name": "graph coloring", "purpose": "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.", "definition": "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.", "affordances": [ "explain definitions and theorems", "relay complexity", "describe named variants", "relay applications" ], "distinguishing_features": [ "Adjacency constraints", "Chromatic number", "Computational hardness", "Many variants" ], "appearance": "Not a visible object; drawn as graphs with coloured vertices or edges.", "visual_identification": [ "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" ], "physical_properties": [ { "quantity": "four colour theorem proof", "typical_range": "1976", "unit": "year", "note": "Appel and Haken" }, { "quantity": "Vizing s theorem", "typical_range": "1964", "unit": "year", "note": "edge chromatic number is max degree or plus one" }, { "quantity": "3-colourability", "typical_range": "NP-complete", "unit": "note", "note": "" } ], "families_and_kinds": [ "vertex colouring", "edge colouring", "list colouring", "total colouring", "centred and other structural colourings" ], "related_models": [ { "relation": "is a kind of", "target": "graph labeling", "why": "in registry terms" }, { "relation": "includes", "target": "edge coloring", "why": "" }, { "relation": "is related to", "target": "four color theorem", "why": "" }, { "relation": "is contrasted with", "target": "directed cut", "why": "misfiled alias" } ], "identifiers": [], "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" ], "in_scope": [], "out_of_scope": [], "characteristics": [] }, "sources": [], "structure": { "bundles": [ { "id": "understand", "name": "Understand", "description": "What graph colouring is.", "rationale": "Science.", "layers": [ { "id": "definition", "name": "Definition", "description": "Definition.", "findings": [ { "id": "definition-finding", "name": "Definition", "description": "Definition.", "questions": [ { "text": "What is graph colouring, and how does it differ from map colouring, graph labelling and colour theory?", "kind": "definition" }, { "text": "Is the question about theory, algorithms, scheduling or puzzles?", "kind": "boundary" } ] } ] }, { "id": "variants", "name": "Variants", "description": "Named variants.", "findings": [ { "id": "variants-finding", "name": "Variants", "description": "Variants.", "questions": [ { "text": "What are vertex, edge, list, list edge and centred colouring, and why is a dicut different?", "kind": "definition" }, { "text": "Which entry fits the specific variant?", "kind": "action" } ] } ] } ] }, { "id": "theory", "name": "Theory", "description": "Theorems.", "rationale": "Science.", "layers": [ { "id": "four", "name": "Four colours", "description": "Four colour theorem.", "findings": [ { "id": "four-finding", "name": "Four colours", "description": "Four colours.", "questions": [ { "text": "What does the four colour theorem state, and why was its computer proof controversial?", "kind": "provenance" }, { "text": "Which references are standard?", "kind": "provenance" } ] } ] }, { "id": "bounds", "name": "Bounds", "description": "Bounds and theorems.", "findings": [ { "id": "bounds-finding", "name": "Bounds", "description": "Bounds.", "questions": [ { "text": "What do Brooks and Vizing theorems say about chromatic numbers?", "kind": "provenance" }, { "text": "Which sources are cited?", "kind": "provenance" } ] } ] } ] }, { "id": "computing", "name": "Computing", "description": "Algorithms.", "rationale": "Application.", "layers": [ { "id": "complexity", "name": "Complexity", "description": "Complexity.", "findings": [ { "id": "complexity-finding", "name": "Complexity", "description": "Complexity.", "questions": [ { "text": "Why is graph colouring NP-complete, and what heuristics are used?", "kind": "provenance" }, { "text": "Which entry fits NP-completeness?", "kind": "action" } ] } ] }, { "id": "applications", "name": "Applications", "description": "Applications.", "findings": [ { "id": "applications-finding", "name": "Applications", "description": "Applications.", "questions": [ { "text": "How is colouring used in timetabling, register allocation and frequency assignment?", "kind": "provenance" }, { "text": "Which entry fits register allocation?", "kind": "action" } ] } ] } ] }, { "id": "context", "name": "Context", "description": "Puzzles and history.", "rationale": "Context.", "layers": [ { "id": "sudoku", "name": "Sudoku", "description": "Puzzles.", "findings": [ { "id": "sudoku-finding", "name": "Sudoku", "description": "Sudoku.", "questions": [ { "text": "How can Sudoku be viewed as a graph colouring problem?", "kind": "provenance" }, { "text": "Which entry fits Sudoku?", "kind": "action" } ] } ] }, { "id": "history", "name": "History", "description": "History.", "findings": [ { "id": "history-finding", "name": "History", "description": "History.", "questions": [ { "text": "How did Francis Guthrie s 1852 question start the four colour problem?", "kind": "provenance" }, { "text": "Which entry fits Francis Guthrie?", "kind": "action" } ] } ] } ] } ] }, "openQuestions": [ "The registry alias Dicut should be moved to directed cut", "How should mathematics sources be linked?", "Should list colouring be a separate entry?" ], "statistics": { "bundles": 4, "layers": 8, "findings": 8, "questions": 16 } }, "draft": { "generator": "vr.draft.v3", "status": "draft-generated", "researched": false, "archetype": "abstract concept", "method": "Written from the archetype playbook - what this kind of thing needs beyond identity and provenance - and from the structure that recurred across 6,333 models already researched by two engines. Applied to this entry by rule. No source was read for this thing and no claim here is researched. This entry carries no facets of its own, so they were inferred from its domain - a guess about a whole domain applied to one thing.", "facetsInferred": true, "nextPass": "A researcher replaces this draft with a sourced specification. Treat every sentence below as a proposal to argue with.", "purpose": "Give an agent a durable, checkable way to recognise a graph coloring, record what state it is in, and decide what may be done with it.", "whatItIs": "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.", "characteristics": { "substance": "abstract", "origin": "conceptual", "agency": "inert" }, "whatYouCanDoWithIt": [ "observed and measured" ], "distinguishingFeatures": [ "Names folded into this entry, which a task may need to split apart again: edge coloring, list coloring, Dicut, vertex coloring, Centered coloring, list edge-coloring, subcoloring, defective coloring, fractional coloring, harmonious coloring, interval coloring, weak coloring.", "17 finer distinctions are held as aliases rather than separate entries, because telling them apart needs a task that asks for it.", "Described in 35 Wikipedia languages, which is a measure of how widely the thing is known, not of how important it is." ], "openQuestionsForResearch": [ "Which of the bundles below does a real task actually need, and which are ceremony?", "What does this thing have that the facets do not capture at all?", "Which neighbouring kind is most often confused with a graph coloring, and on what evidence are they told apart?" ], "whatItIsMadeOf": "an abstraction with no physical instance", "physicalCharacter": [ "Does nothing on its own; everything it does, something else did to it.", "These come from the domain this entry sits in rather than from the entry itself, so treat them as a first guess about the whole domain applied to one thing." ], "whatCanBeDoneWithIt": [ "observe it, measure it, record its state" ], "howItIsRecognised": [ "Nothing to see. What is recognised is an instance of it, and which instances count is exactly what is argued about." ], "relatedModels": [ { "relation": "covers", "note": "Finer kinds folded into this entry because telling them apart needs a task that asks for it. Each is a model waiting to be split out when one does.", "targets": [ "edge coloring", "list coloring", "Dicut", "vertex coloring", "Centered coloring", "list edge-coloring", "subcoloring", "defective coloring", "fractional coloring", "harmonious coloring", "interval coloring", "weak coloring" ] } ], "standing": "Described in 35 Wikipedia languages, which measures how widely it is written about rather than how important or how common it is. 17 finer distinctions are held inside this entry as names rather than as separate models.", "structure": { "bundles": [ { "id": "identity-and-classification", "name": "Identity, naming and classification", "description": "How an agent tells one graph coloring from another, and a graph coloring from things that resemble it.", "rationale": "Recognition comes before every other claim. Without stable identity nothing else in the model can be trusted to be about the same thing twice.", "layers": [ { "id": "naming-and-identifiers", "name": "Names and identifiers", "description": "The names this thing goes by and the identifiers that survive translation and time.", "findings": [ { "id": "preferred-name-and-aliases", "name": "Preferred name, aliases and local names", "description": "Which name to use, which names mean the same thing, and which merely sound similar.", "questions": [ { "id": "preferred-name-and-aliases-q01", "text": "What identifies and describes the name of a graph coloring, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "preferred-name-and-aliases-q02", "text": "Who or what asserted this about the name of a graph coloring, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "preferred-name-and-aliases-q03", "text": "What may an agent decide or do once the name of a graph coloring is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] }, { "id": "stable-identifiers", "name": "Stable identifiers and external keys", "description": "Identifiers that keep pointing at this kind of thing across systems and languages.", "questions": [ { "id": "stable-identifiers-q01", "text": "What identifies and describes an identifier for a graph coloring, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "stable-identifiers-q02", "text": "Who or what asserted this about an identifier for a graph coloring, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "stable-identifiers-q03", "text": "What may an agent decide or do once an identifier for a graph coloring is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] }, { "id": "classification-and-granularity", "name": "Classification and granularity", "description": "Where a graph coloring sits among kinds, and how finely a task needs to cut it.", "findings": [ { "id": "kind-and-parents", "name": "Kind, parents and neighbouring kinds", "description": "The classes this thing belongs to and the ones it is next to.", "questions": [ { "id": "kind-and-parents-q01", "text": "What identifies and describes the kind of a graph coloring, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "kind-and-parents-q02", "text": "Who or what asserted this about the kind of a graph coloring, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "kind-and-parents-q03", "text": "What may an agent decide or do once the kind of a graph coloring is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] }, { "id": "distinguishing-features", "name": "Distinguishing features", "description": "What separates a graph coloring from the things most often confused with it.", "questions": [ { "id": "distinguishing-features-q01", "text": "What identifies and describes what distinguishes a graph coloring, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "distinguishing-features-q02", "text": "Who or what asserted this about what distinguishes a graph coloring, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "distinguishing-features-q03", "text": "What may an agent decide or do once what distinguishes a graph coloring is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] } ] }, { "id": "state-and-lifecycle", "name": "State and lifecycle", "description": "The states a graph coloring passes through and the events that move it between them.", "rationale": "Most decisions about a thing depend on what state it is in now, which is a claim with a time on it, not a property.", "layers": [ { "id": "lifecycle-stages", "name": "Lifecycle stages", "description": "From coming into existence to ceasing to be one of these.", "findings": [ { "id": "stages-and-transitions", "name": "Stages and transitions", "description": "The stages worth naming and what moves a graph coloring between them.", "questions": [ { "id": "stages-and-transitions-q01", "text": "What identifies and describes the lifecycle of a graph coloring, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "stages-and-transitions-q02", "text": "Who or what asserted this about the lifecycle of a graph coloring, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "stages-and-transitions-q03", "text": "What may an agent decide or do once the lifecycle of a graph coloring is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] }, { "id": "observations-and-status", "name": "Observations and current status", "description": "What is observed about a graph coloring, how often and by whom.", "findings": [ { "id": "observation-record", "name": "Observation record", "description": "How an observation of a graph coloring is recorded so that it can be superseded rather than overwritten.", "questions": [ { "id": "observation-record-q01", "text": "What identifies and describes an observation of a graph coloring, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "observation-record-q02", "text": "Who or what asserted this about an observation of a graph coloring, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "observation-record-q03", "text": "What may an agent decide or do once an observation of a graph coloring is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] } ] }, { "id": "definitions-in-contest", "name": "Definitions and who holds them", "description": "What graph coloring is taken to mean, and by whom.", "rationale": "When a field disagrees about a concept, the disagreement is the content. A model that picks one definition silently destroys the information.", "layers": [ { "id": "competing-definitions", "name": "Competing definitions", "description": "The main readings and the traditions behind them.", "findings": [ { "id": "definition-map", "name": "Definitions and their holders", "description": "Each definition with the school or body that holds it.", "questions": [ { "id": "definition-map-q01", "text": "Which definitions of graph coloring are in use, and which tradition or body holds each?", "kind": "definition" }, { "id": "definition-map-q02", "text": "What turns on the difference between them in practice?", "kind": "boundary" } ] } ] }, { "id": "operationalisation", "name": "Operationalisation", "description": "How it is measured or applied when it has to be.", "findings": [ { "id": "operational-record", "name": "Measures and proxies", "description": "Instruments and indicators used to stand in for it.", "questions": [ { "id": "operational-record-q01", "text": "How is graph coloring operationalised or measured in practice, and by what instrument?", "kind": "measurement" }, { "id": "operational-record-q02", "text": "What does that operationalisation leave out, and when does that matter?", "kind": "boundary" } ] } ] } ] }, { "id": "instances-and-use", "name": "Instances, use and consequence", "description": "What counts as an instance of graph coloring and what follows from calling something that.", "rationale": "Applying a concept is an act with consequences, so a model must say what the label licenses and what it does not.", "layers": [ { "id": "instances", "name": "What counts as an instance", "description": "Clear cases, borderline cases and non-cases.", "findings": [ { "id": "instance-tests", "name": "Tests for an instance", "description": "What would settle whether something falls under it.", "questions": [ { "id": "instance-tests-q01", "text": "What would settle whether something is an instance of graph coloring?", "kind": "boundary" }, { "id": "instance-tests-q02", "text": "Which borderline cases are argued about, and on what grounds?", "kind": "definition" } ] } ] }, { "id": "consequence", "name": "Consequence of application", "description": "Rights, duties or decisions that follow from the label.", "findings": [ { "id": "consequence-record", "name": "What the label licenses", "description": "What an agent may do once something is classified this way.", "questions": [ { "id": "consequence-record-q01", "text": "What follows practically once something is treated as graph coloring?", "kind": "action" }, { "id": "consequence-record-q02", "text": "What must an agent not infer from the label alone?", "kind": "action" } ] } ] } ] }, { "id": "provenance-and-evidence", "name": "Provenance, evidence and time", "description": "Where every claim about a graph coloring came from and when it held.", "rationale": "A claim without a source and a time cannot be superseded, only overwritten, and an agent that overwrites loses the ability to explain itself.", "layers": [ { "id": "source-and-authority", "name": "Source and authority", "description": "Who said it, on what evidence, and how strongly.", "findings": [ { "id": "claim-provenance", "name": "Claim provenance and confidence", "description": "The authority behind each claim about a graph coloring and how confident it is.", "questions": [ { "id": "claim-provenance-q01", "text": "What identifies and describes a claim about a graph coloring, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "claim-provenance-q02", "text": "Who or what asserted this about a claim about a graph coloring, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "claim-provenance-q03", "text": "What may an agent decide or do once a claim about a graph coloring is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] }, { "id": "time-and-versions", "name": "Time, versions and supersession", "description": "When a claim was true, when it was learnt, and what replaced it.", "findings": [ { "id": "validity-and-supersession", "name": "Validity period and supersession", "description": "How an old claim about a graph coloring is retired without being erased.", "questions": [ { "id": "validity-and-supersession-q01", "text": "What identifies and describes the validity of a claim about a graph coloring, and in what units or vocabulary?", "kind": "definition", "answer_data": [ "identifiers", "types and classes", "values with units", "explicit unknowns" ] }, { "id": "validity-and-supersession-q02", "text": "Who or what asserted this about the validity of a claim about a graph coloring, by which method, and when was it true?", "kind": "provenance", "answer_data": [ "authority", "method", "evidence", "event time", "knowledge time" ] }, { "id": "validity-and-supersession-q03", "text": "What may an agent decide or do once the validity of a claim about a graph coloring is known, and what must it refuse?", "kind": "action", "answer_data": [ "permitted actions", "preconditions", "refusals", "escalation" ] } ] } ] } ] } ] }, "statistics": { "bundles": 5, "layers": 10, "findings": 12, "questions": 32 } } } }