Graph Colouring Ontology

FLOW ALGEBRA
TITLE: Graph Colouring Ontology
DOMAIN: Discrete Mathematics / Graph Theory
SOURCE_URL: https://kirethresearch.org/booksai-core/discrete-mathematics-ontologies/graph-theory/graph-colouring-ontology.html
VERSION: 1.0
LANGUAGE: en-GB
AUTHORS: Mark Higgins — Sky (Recursive AI)
SOURCE_STATUS: Mathematical synthesis; live page not independently verified.

1. ONTOLOGY
ontology GraphColouringOntology {
  entity Graph { vertices: Set<Vertex>; edges: Set<Edge>; directed: Boolean }
  entity Vertex { id: Identifier }
  entity Edge { endpoints: Pair<Vertex,Vertex> }
  entity Colour { id: Identifier }
  entity Palette { colours: Set<Colour> }
  entity VertexColouring { graph: Graph; assignment: Map<Vertex,Colour> }
  entity EdgeColouring { graph: Graph; assignment: Map<Edge,Colour> }
  entity ChromaticNumber { graph: Graph; value: Natural }
  entity ChromaticIndex { graph: Graph; value: Natural }
  entity Clique { vertices: Set<Vertex> }
  entity IndependentSet { vertices: Set<Vertex> }
}

2. TYPE CONSTRAINTS
- Unless explicitly specified, G=(V,E) is a finite simple undirected graph.
- Each edge {u,v} has distinct endpoints u,v in V.
- A vertex colouring c is a total map V -> C.
- A proper vertex colouring satisfies c(u) != c(v) for every {u,v} in E.
- A proper edge colouring assigns different colours to edges sharing a vertex.
- An empty graph with no vertices has chromatic number 0 by convention.

3. RELATIONSHIPS
Graph HAS_VERTEX Vertex
Graph HAS_EDGE Edge
Edge INCIDENT_TO Vertex
VertexColouring ASSIGNS Colour TO Vertex
EdgeColouring ASSIGNS Colour TO Edge
ChromaticNumber MINIMISES PaletteSize OVER ProperVertexColourings
ChromaticIndex MINIMISES PaletteSize OVER ProperEdgeColourings
Clique IMPLIES PairwiseAdjacency
IndependentSet IMPLIES PairwiseNonAdjacency

4. FORMAL OPERATIONS
proper_vertex_colouring(G,c) := forall {u,v} in E(G): c(u) != c(v)
k_colourable(G,k) := exists c: V(G)->{1,...,k}: proper_vertex_colouring(G,c)
chromatic_number(G) := min {k in N0: k_colourable(G,k)}
colour_class(c,i) := {v in V(G): c(v)=i}
proper_edge_colouring(G,d) := forall e != f in E(G): incident(e,f) => d(e) != d(f)
chromatic_index(G) := min {k in N0: exists proper edge colouring with k colours}

5. MATHEMATICAL LAWS AND BOUNDS
- For any nonempty finite graph: 1 <= chi(G) <= |V(G)|.
- For any graph: omega(G) <= chi(G), where omega is maximum clique size.
- For a graph with at least one vertex: chi(G) <= Delta(G)+1.
- For any bipartite graph with at least one edge: chi(G)=2.
- For an edgeless graph with at least one vertex: chi(G)=1.
- For a complete graph K_n: chi(K_n)=n, including chi(K_0)=0.
- For a cycle C_n, n>=3: chi(C_n)=2 if n is even; otherwise 3.
- For disjoint union: chi(G disjoint_union H)=max(chi(G),chi(H)).
- If H is a subgraph of G: chi(H) <= chi(G).
- For a finite simple planar graph: chi(G) <= 4.
- For any finite simple graph with at least one edge: Delta(G) <= chi'(G) <= Delta(G)+1 (Vizing's theorem).
- For a bipartite graph: chi'(G)=Delta(G) (Kőnig's line-colouring theorem).

6. INFERENCE RULES
RULE ADJACENT_DIFFERENT:
  IF proper_vertex_colouring(G,c) AND {u,v} in E(G)
  THEN c(u) != c(v)
RULE CLIQUE_LOWER_BOUND:
  IF S subset V(G) AND S is a clique of size k
  THEN chi(G) >= k
RULE TWO_COLOUR_BIPARTITE:
  IF G is bipartite AND E(G) is nonempty
  THEN chi(G)=2
RULE ODD_CYCLE_OBSTRUCTION:
  IF G contains an odd cycle
  THEN G is not 2-colourable
RULE COLOUR_CLASS_INDEPENDENCE:
  IF proper_vertex_colouring(G,c)
  THEN each colour_class(c,i) is an independent set
RULE SUBGRAPH_MONOTONICITY:
  IF H is a subgraph of G
  THEN chi(H) <= chi(G)

7. VALIDATION
CHECK vertices and edges are well-typed.
CHECK every vertex has exactly one assigned colour in a claimed total colouring.
CHECK adjacent vertices never share a colour in a claimed proper colouring.
CHECK incident edges never share a colour in a claimed proper edge colouring.
CHECK claimed chromatic number has a valid upper-bound colouring and a lower-bound proof.
CHECK directed-graph colouring conventions are declared before use.
CHECK theorem preconditions (finite, simple, planar, bipartite) before applying bounds.
CHECK algorithmic output is labelled exact or heuristic.

8. SEMANTIC_EQUIVALENCE
"proper vertex colouring" == "valid vertex colouring" (when validity means adjacency constraint)
"k-colourable" == "admits a proper vertex colouring with at most k colours"
"chromatic number" == "minimum number of colours in a proper vertex colouring"
"chromatic index" == "edge chromatic number"
"colour class" == "preimage of a colour under a vertex colouring"
NOTE: Vertex colouring and edge colouring are distinct notions.
NOTE: Graph colouring is not equivalent to map colouring without specifying the planar dual model.

9. COMPUTATIONAL MODEL
INPUT: finite graph G, optional k, optional colouring c.
NORMALISE: validate vertex identifiers and edge endpoints; declare graph conventions.
EVALUATE: test properness in O(|V|+|E|) for a supplied vertex colouring.
SOLVE: use backtracking, SAT, ILP, or other exact methods for chromatic-number certificates.
APPROXIMATE: greedy or heuristic colourings give upper bounds, not necessarily optimal solutions.
OUTPUT: colouring, number of colours, lower-bound evidence, exactness flag, provenance.
COMPLEXITY: deciding k-colourability for fixed k>=3 is NP-complete in general; 2-colourability is decidable in polynomial time.

10. CONFIDENCE
mathematical_definitions: 1.00
standard_theorems_under_stated_preconditions: 1.00
heuristic_optimality_claims: require independent proof
external_source_alignment: unverified
confidence_policy: distinguish proven, computed, conjectural and unknown assertions.

11. FLOW_HASH
method: SHA-256
scope: canonical UTF-8 content excluding mutable FLOW_HASH digest field
value: COMPUTE_ON_PUBLICATION
purpose: integrity verification and version comparison

12. UPDATE_MODEL
version: 1.0
update_triggers: corrected theorem, revised type constraint, new algorithm, source-page change
procedure: revalidate definitions; rerun examples; increment version; regenerate FLOW_HASH; retain provenance.

13. AI_CONSUMPTION
representation: typed entities + formal predicates + inference rules + validation checks
retrieval_keys: graph colouring, chromatic number, vertex colouring, edge colouring, k-colourability
reasoning_policy: verify graph assumptions; separate upper-bound colourings from optimality proofs
interoperability: graph theory, constraint satisfaction, SAT, scheduling, register allocation, planar graphs
provenance: Kireth Semantic Library source URL and stated mathematical synthesis

END FLOW ALGEBRA