# Chromatic certificate check

`chromatic-certificate-check` · version 1.0.0 · Numbers & math · free, no key needed

Check a claim chi(G) = k: a proper k-colouring plus a clique or bounded exhaustive proof; returns the first discrepancy.

**Use when you need to: check a chromatic number claim · verify a chromatic number certificate · prove a graph is not k-1 colorable.**

## Decide before calling

Read the [versioned contract](/v1/tools/chromatic-certificate-check/versions/1.0.0) and the supported scope below. Reuse `chromatic-certificate-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 `chromatic-certificate-check@1.0.0` for check a chromatic number claim. 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 chromatic number claim
- verify a chromatic number certificate
- prove a graph is not k-1 colorable
- exact chromatic number check for a small graph
- validate chi(G) answer with clique and coloring
- is the chromatic number really k
- check the minimum number of colors for a graph

## Not supported

- compute the chromatic number without a supplied colouring
- exhaustive lower-bound proofs for graphs over 32 nodes or beyond 1,000,000 search steps
- chromatic index (edge colouring), list or fractional chromatic number
- directed graphs, multigraphs or self-loops

## Behavior

- Reference: R. Diestel, Graph Theory, 5th ed. (GTM 173, Springer 2017), chapter 5 (k-colouring, chi(G) = least k with a k-colouring) and section 5.5 (chi(G) >= omega(G)); every output carries reference_version "diestel-gtm173-5e-2017".
- Graph: simple undirected; duplicate_node, unknown_edge_endpoint, self_loop, duplicate_edge and empty ids are invalid_input (details.reason). Node ids are exact strings (no Unicode normalization), at most 64 UTF-8 bytes, no lone surrogates.
- Claim chi(G) = k (chromatic_number 0..256). Upper bound: coloring (node id -> integer label 0..2147483647, not -0) must be proper and use exactly k distinct labels; fewer labels refute the claim (coloring_below_claim), more fail it (coloring_exceeds_claim).
- lower_bound "clique": clique (required) must list exactly k distinct pairwise adjacent nodes. lower_bound "exhaustive": clique must be absent; allowed for at most 32 nodes; every colouring with k-1 labels is searched, at most 1,000,000 steps, else limit_exceeded.
- Exhaustive order: nodes in array order; node i tries labels 0..min(k-2, 1 + largest earlier label) ascending (restricted growth); each try is one step; the first proper colouring found is the lexicographically least with at most k-1 labels, returned as witness_colors aligned with nodes.
- Check order: uncolored_node, unknown_node (code point order), monochromatic_edge (edge order), coloring_exceeds_claim / coloring_below_claim, then clique checks (unknown_node / duplicate_member per position, missing_edge over pairs i < j, clique_too_small) or smaller_coloring_exists.
- A true claim with an insufficient certificate is invalid: the tool checks the certificate. verified_chromatic_number = k when valid, else null.

## 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
- `chromatic_number` (integer, required): min 0; max 256
- `coloring` (object, required)
- `lower_bound` (one of "clique", "exhaustive", required)
- `clique` (array of string, optional): max items 256; each min length 1

## Output

- `valid` (boolean, required)
- `reason` (one of "uncolored_node", "unknown_node", "monochromatic_edge", "coloring_exceeds_claim", "coloring_below_claim", "duplicate_member", "missing_edge", "clique_too_small", "smaller_coloring_exists", 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
- `lower_bound` (one of "clique", "exhaustive", required)
- `verified_chromatic_number` (integer or null, 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
- max clique items: 256
- max exhaustive nodes: 32
- max search steps: 1000000

## Example

Request input:

```json
{
  "nodes": [
    "a",
    "b",
    "c",
    "d",
    "e"
  ],
  "edges": [
    [
      "a",
      "b"
    ],
    [
      "b",
      "c"
    ],
    [
      "c",
      "d"
    ],
    [
      "d",
      "e"
    ],
    [
      "e",
      "a"
    ]
  ],
  "chromatic_number": 3,
  "coloring": {
    "a": 0,
    "b": 1,
    "c": 0,
    "d": 1,
    "e": 2
  },
  "lower_bound": "exhaustive"
}
```

Response:

```json
{
  "result": {
    "valid": true,
    "reason": null,
    "first_discrepancy": null,
    "node_count": 5,
    "edge_count": 5,
    "color_count": 3,
    "lower_bound": "exhaustive",
    "verified_chromatic_number": 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": "chromatic-certificate-check",
  "version": "1.0.0",
  "input": {
    "nodes": [
      "a",
      "b",
      "c",
      "d",
      "e"
    ],
    "edges": [
      [
        "a",
        "b"
      ],
      [
        "b",
        "c"
      ],
      [
        "c",
        "d"
      ],
      [
        "d",
        "e"
      ],
      [
        "e",
        "a"
      ]
    ],
    "chromatic_number": 3,
    "coloring": {
      "a": 0,
      "b": 1,
      "c": 0,
      "d": 1,
      "e": 2
    },
    "lower_bound": "exhaustive"
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/chromatic-certificate-check/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"nodes":["a","b","c","d","e"],"edges":[["a","b"],["b","c"],["c","d"],["d","e"],["e","a"]],"chromatic_number":3,"coloring":{"a":0,"b":1,"c":0,"d":1,"e":2},"lower_bound":"exhaustive"}'
```

The machine-readable contract is at [/v1/tools/chromatic-certificate-check/versions/1.0.0](/v1/tools/chromatic-certificate-check/versions/1.0.0).

### CLI

```sh
node cli.mjs run chromatic-certificate-check 1.0.0 --input input.json --base-url https://computefirst.net
```

Get the client at [/clients/cli/](/clients/cli/).

## Related tools

- [Coloring count check](/tools/coloring-count-check): Check a proper indexed coloring and an exact canonical-decimal claim for its number of distinct colors.
- [Graph coloring check](/tools/graph-coloring-check): Check that a node colouring of an undirected graph is proper (and within k colours); returns the first conflict.
- [Lp optimality certificate check](/tools/lp-optimality-certificate-check): Check an LP optimum claim from a primal x and dual y: feasibility, complementary slackness and zero duality gap.
- [Graph clique check](/tools/graph-clique-check): Check that listed nodes form a clique (optionally maximal, of a minimum size); returns the first missing 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.
- [Linear inconsistency certificate check](/tools/linear-inconsistency-certificate-check): Check a witness y that A x = b has no solution (yA = 0, yb != 0) or no x >= 0 solution (Farkas: yA >= 0, yb < 0).