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

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

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

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

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.

CLI

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

Get the client at /clients/cli/.

Related tools

• Coloring count check: Check a proper indexed coloring and an exact canonical-decimal claim for its number of distinct colors.
• 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: Check an LP optimum claim from a primal x and dual y: feasibility, complementary slackness and zero duality gap.
• 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: Check a claimed max flow with a min-cut certificate or residual search; reports the first failure or augmenting path.
• 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).