{"id":"graph-coloring-check","version":"1.0.0","description":"Check that a node colouring of an undirected graph is proper (and within k colours); returns the first conflict.","supported_operations":["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","בדיקת צביעת גרף"],"unsupported_operations":["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"],"semantics":["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."],"limits":{"max_nodes":256,"max_edges":4096,"max_node_id_bytes":64,"max_coloring_keys":256},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["nodes","edges","coloring"],"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}}},"coloring":{"type":"object","maxProperties":256,"additionalProperties":{"type":"integer","minimum":0,"maximum":2147483647}},"max_colors":{"type":"integer","minimum":0,"maximum":256}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reason","first_discrepancy","node_count","edge_count","color_count","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":["string","null"],"enum":["uncolored_node","unknown_node","monochromatic_edge","too_many_colors",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},"max_colors":{"type":"integer","minimum":0}}},"node_count":{"type":"integer","minimum":0},"edge_count":{"type":"integer","minimum":0},"color_count":{"type":"integer","minimum":0},"reference_version":{"type":"string","const":"diestel-gtm173-5e-2017"}}},"examples":[{"input":{"nodes":["a","b","c"],"edges":[["a","b"],["b","c"],["a","c"]],"coloring":{"a":0,"b":1,"c":2},"max_colors":3},"output":{"valid":true,"reason":null,"first_discrepancy":null,"node_count":3,"edge_count":3,"color_count":3,"reference_version":"diestel-gtm173-5e-2017"}},{"input":{"nodes":["a","b","c"],"edges":[["a","b"],["b","c"],["a","c"]],"coloring":{"a":0,"b":1,"c":0}},"output":{"valid":false,"reason":"monochromatic_edge","first_discrepancy":{"edge_index":2,"edge":["a","c"],"color":0},"node_count":3,"edge_count":3,"color_count":2,"reference_version":"diestel-gtm173-5e-2017"}}],"execute_url":"/v1/tools/graph-coloring-check/versions/1.0.0/execute"}