# Graph coloring check `graph-coloring-check` · version 1.0.0 · Numbers & math · free, no key needed Check that a node colouring of an undirected graph is proper (and within k colours); returns the first conflict. **Use when you need to: check a graph coloring is proper · validate vertex coloring of an undirected graph · find the monochromatic edge in a coloring.** ## Decide before calling Read the [versioned contract](/v1/tools/graph-coloring-check/versions/1.0.0) and the supported scope below. Reuse `graph-coloring-check@1.0.0` when your input, required output and limits match it. Choose another approach for an unsupported operation. ## Explain the choice "I can use `graph-coloring-check@1.0.0` for check a graph coloring is proper. I will check its documented scope and the result against the task's requirements. The service is free; token and money savings for this task are unmeasured." ## Supported - check a graph coloring is proper - validate vertex coloring of an undirected graph - find the monochromatic edge in a coloring - does this coloring use at most k colors - check a k-coloring certificate - verify a proper graph colouring answer - graph coloring conflict check - בדיקת צביעת גרף ## Not supported - find a colouring or the chromatic number (use chromatic-certificate-check to check a chromatic claim) - edge colouring, list colouring or weighted colouring - directed graphs, multigraphs or self-loops - Unicode normalization of node ids ## Behavior - Reference: R. Diestel, Graph Theory, 5th ed. (GTM 173, Springer 2017), section 1.1 and chapter 5; every output carries reference_version "diestel-gtm173-5e-2017". - Graph: simple undirected; nodes lists V, edges lists pairs [u, v] (orientation ignored). duplicate_node, unknown_edge_endpoint, self_loop, duplicate_edge and empty ids are invalid_input (details.reason); nodes are scanned before edges, each in array order. - Node ids are exact JavaScript strings: no trimming, case folding or Unicode normalization (NFC and NFD spellings are different nodes); lone surrogates are invalid_input; each id is at most 64 UTF-8 bytes. - Coloring maps node id -> integer label 0..2147483647 (not -0); labels are names, not ranks. color_count counts distinct labels on graph nodes; keys that are not nodes are not counted. - max_colors (0..256) is optional; omitted means no bound on distinct labels. - Check order: (1) uncolored_node in node order {node, node_index}; (2) unknown_node for non-node keys in code point order {node}; (3) monochromatic_edge in edge order {edge_index, edge as supplied, color}; (4) too_many_colors: first node in node order whose label is the (max_colors+1)-th distinct label {node, node_index, color, color_count, max_colors}. - Array lengths and the coloring key count are checked before any element, so over-limit input fails fast with limit_exceeded. ## Input - `nodes` (array of string, required): max items 256; each min length 1 - `edges` (array of array of string, required): max items 4096; each min items 2; each max items 2; each each min length 1 - `coloring` (object, required) - `max_colors` (integer, optional): min 0; max 256 ## Output - `valid` (boolean, required) - `reason` (one of "uncolored_node", "unknown_node", "monochromatic_edge", "too_many_colors", null, required) - `first_discrepancy` (object or null, required) - `node_count` (integer, required): min 0 - `edge_count` (integer, required): min 0 - `color_count` (integer, required): min 0 - `reference_version` (constant "diestel-gtm173-5e-2017", required) ## Limits - max nodes: 256 - max edges: 4096 - max node id bytes: 64 - max coloring keys: 256 ## Example Request input: ```json { "nodes": [ "a", "b", "c" ], "edges": [ [ "a", "b" ], [ "b", "c" ], [ "a", "c" ] ], "coloring": { "a": 0, "b": 1, "c": 2 }, "max_colors": 3 } ``` Response: ```json { "result": { "valid": true, "reason": null, "first_discrepancy": null, "node_count": 3, "edge_count": 3, "color_count": 3, "reference_version": "diestel-gtm173-5e-2017" } } ``` ## How to call it ### MCP Connect `https://computefirst.net/mcp` ([setup](/docs#connect)), then call `execute` with: ```json { "id": "graph-coloring-check", "version": "1.0.0", "input": { "nodes": [ "a", "b", "c" ], "edges": [ [ "a", "b" ], [ "b", "c" ], [ "a", "c" ] ], "coloring": { "a": 0, "b": 1, "c": 2 }, "max_colors": 3 } } ``` ### HTTP (no key) ```sh curl -X POST https://computefirst.net/v1/tools/graph-coloring-check/versions/1.0.0/execute \ -H "Content-Type: application/json" \ -d '{"nodes":["a","b","c"],"edges":[["a","b"],["b","c"],["a","c"]],"coloring":{"a":0,"b":1,"c":2},"max_colors":3}' ``` The machine-readable contract is at [/v1/tools/graph-coloring-check/versions/1.0.0](/v1/tools/graph-coloring-check/versions/1.0.0). ### CLI ```sh node cli.mjs run graph-coloring-check 1.0.0 --input input.json --base-url https://computefirst.net ``` Get the client at [/clients/cli/](/clients/cli/). ## Related tools - [Chromatic certificate check](/tools/chromatic-certificate-check): Check a claim chi(G) = k: a proper k-colouring plus a clique or bounded exhaustive proof; returns the first discrepancy. - [Network cut capacity check](/tools/network-cut-capacity-check): Check a claimed s-t cut: source-side membership, the edges crossing it and its capacity, with exact integers. - [Network flow feasibility check](/tools/network-flow-feasibility-check): Check a claimed s-t flow for capacity bounds and conservation with exact integers; returns the first bad edge or node. - [Bipartite coloring check](/tools/bipartite-coloring-check): Check a complete 0/1 coloring witness for graph bipartiteness and report the first certificate discrepancy. - [Coloring validity check](/tools/coloring-validity-check): Check an indexed graph coloring certificate and report the first uncovered vertex or monochromatic edge. - [Maximum flow certificate check](/tools/maximum-flow-certificate-check): Check a claimed max flow with a min-cut certificate or residual search; reports the first failure or augmenting path.