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 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:

{
  "nodes": [
    "a",
    "b",
    "c"
  ],
  "edges": [
    [
      "a",
      "b"
    ],
    [
      "b",
      "c"
    ],
    [
      "a",
      "c"
    ]
  ],
  "coloring": {
    "a": 0,
    "b": 1,
    "c": 2
  },
  "max_colors": 3
}

Response:

{
  "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), then call execute with:

{
  "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)

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.

CLI

node cli.mjs run graph-coloring-check 1.0.0 --input input.json --base-url https://computefirst.net

Get the client at /clients/cli/.

Related 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: Check a claimed s-t cut: source-side membership, the edges crossing it and its capacity, with exact integers.
• 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: Check a complete 0/1 coloring witness for graph bipartiteness and report the first certificate discrepancy.
• Coloring validity check: Check an indexed graph coloring certificate and report the first uncovered vertex or monochromatic edge.
• Maximum flow certificate check: Check a claimed max flow with a min-cut certificate or residual search; reports the first failure or augmenting path.