{"id":"coloring-validity-check","version":"1.0.0","description":"Check an indexed graph coloring certificate and report the first uncovered vertex or monochromatic edge.","supported_operations":["check graph coloring validity","validate a vertex color assignment","find first coloring conflict","check proper graph coloring certificate","verify every vertex has a color","test claimed graph coloring"],"unsupported_operations":["finding or repairing a coloring","computing the chromatic number","accepting endpoint names instead of indices"],"semantics":["Vertices are the indices 0 through vertex_count-1; edges are inspected in supplied array order.","A proper coloring assigns one non-null, non-empty exact Unicode string to every vertex and gives adjacent endpoints unequal strings.","Color equality is exact JavaScript string equality; no normalization, case folding, trimming, or color renaming occurs.","Every verdict names Diestel Graph Theory 5th ed. (2017), sections 1.6 and 5.2; duplicates are checked in place and a self-loop necessarily conflicts.","A false verdict reports coverage discrepancies before edge discrepancies; ties use ascending vertex or edge index."],"limits":{"max_vertices":10000,"max_edges":50000,"max_color_bytes":64},"pricing":{"status":"unpriced","charge_usd":null},"input_schema":{"type":"object","additionalProperties":false,"required":["vertex_count","edges","colors"],"properties":{"vertex_count":{"type":"integer","minimum":0,"maximum":10000},"edges":{"type":"array","maxItems":50000,"items":{"type":"object","additionalProperties":false,"required":["from","to"],"properties":{"from":{"type":"integer","minimum":0,"maximum":9999},"to":{"type":"integer","minimum":0,"maximum":9999}}}},"colors":{"type":"array","maxItems":10000,"items":{"type":["string","null"],"maxLength":64}}}},"output_schema":{"type":"object","additionalProperties":false,"required":["valid","reference_version"],"properties":{"valid":{"type":"boolean"},"reason":{"type":"string"},"discrepancy":{"type":"object","additionalProperties":false,"required":["path","index","expected","actual"],"properties":{"path":{"type":"string"},"index":{"type":"integer","minimum":0},"expected":{"oneOf":[{"type":"string"},{"type":"integer"},{"type":"null"}]},"actual":{"oneOf":[{"type":"string"},{"type":"integer"},{"type":"null"}]}}},"reference_version":{"type":"string"}}},"examples":[{"input":{"vertex_count":3,"edges":[{"from":0,"to":1},{"from":1,"to":2}],"colors":["red","blue","red"]},"output":{"valid":true,"reference_version":"Diestel Graph Theory 5th ed. (2017), sections 1.6 and 5.2"}},{"input":{"vertex_count":2,"edges":[{"from":0,"to":1}],"colors":["x","x"]},"output":{"valid":false,"reason":"monochromatic_edge","discrepancy":{"path":"edges[0]","index":0,"expected":"different endpoint colors","actual":"x"},"reference_version":"Diestel Graph Theory 5th ed. (2017), sections 1.6 and 5.2"}}],"execute_url":"/v1/tools/coloring-validity-check/versions/1.0.0/execute"}