{"id":"chromatic-certificate-check","version":"1.0.0","description":"Check a claim chi(G) = k: a proper k-colouring plus a clique or bounded exhaustive proof; returns the first discrepancy.","supported_operations":["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"],"unsupported_operations":["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"],"semantics":["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."],"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},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["nodes","edges","chromatic_number","coloring","lower_bound"],"properties":{"nodes":{"type":"array","maxItems":256,"items":{"type":"string","minLength":1}},"edges":{"type":"array","maxItems":4096,"items":{"type":"array","minItems":2,"maxItems":2,"items":{"type":"string","minLength":1}}},"chromatic_number":{"type":"integer","minimum":0,"maximum":256},"coloring":{"type":"object","maxProperties":256,"additionalProperties":{"type":"integer","minimum":0,"maximum":2147483647}},"lower_bound":{"type":"string","enum":["clique","exhaustive"]},"clique":{"type":"array","maxItems":256,"items":{"type":"string","minLength":1}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","node_count","edge_count","color_count","lower_bound","verified_chromatic_number","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":["uncolored_node","unknown_node","monochromatic_edge","coloring_exceeds_claim","coloring_below_claim","duplicate_member","missing_edge","clique_too_small","smaller_coloring_exists",null]},"first_discrepancy":{"type":["object","null"],"additionalProperties":false,"properties":{"node":{"type":"string"},"node_index":{"type":"integer","minimum":0},"edge_index":{"type":"integer","minimum":0},"edge":{"type":"array","minItems":2,"maxItems":2,"items":{"type":"string"}},"color":{"type":"integer","minimum":0},"color_count":{"type":"integer","minimum":0},"chromatic_number":{"type":"integer","minimum":0},"position":{"type":"integer","minimum":0},"first_position":{"type":"integer","minimum":0},"nodes":{"type":"array","minItems":2,"maxItems":2,"items":{"type":"string"}},"positions":{"type":"array","minItems":2,"maxItems":2,"items":{"type":"integer","minimum":0}},"clique_size":{"type":"integer","minimum":0},"witness_colors":{"type":"array","maxItems":32,"items":{"type":"integer","minimum":0}},"witness_color_count":{"type":"integer","minimum":0}}},"node_count":{"type":"integer","minimum":0},"edge_count":{"type":"integer","minimum":0},"color_count":{"type":"integer","minimum":0},"lower_bound":{"type":"string","enum":["clique","exhaustive"]},"verified_chromatic_number":{"type":["integer","null"],"minimum":0},"reference_version":{"type":"string","const":"diestel-gtm173-5e-2017"}}},"examples":[{"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"},"output":{"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"}},{"input":{"nodes":["a","b","c","d"],"edges":[["a","b"],["b","c"],["c","d"],["d","a"]],"chromatic_number":3,"coloring":{"a":0,"b":1,"c":0,"d":2},"lower_bound":"exhaustive"},"output":{"valid":false,"reason":"smaller_coloring_exists","first_discrepancy":{"witness_colors":[0,1,0,1],"witness_color_count":2},"node_count":4,"edge_count":4,"color_count":3,"lower_bound":"exhaustive","verified_chromatic_number":null,"reference_version":"diestel-gtm173-5e-2017"}},{"input":{"nodes":["a","b","c"],"edges":[["a","b"],["b","c"],["a","c"]],"chromatic_number":3,"coloring":{"a":0,"b":1,"c":2},"lower_bound":"clique","clique":["a","b","c"]},"output":{"valid":true,"reason":null,"first_discrepancy":null,"node_count":3,"edge_count":3,"color_count":3,"lower_bound":"clique","verified_chromatic_number":3,"reference_version":"diestel-gtm173-5e-2017"}}],"execute_url":"/v1/tools/chromatic-certificate-check/versions/1.0.0/execute"}