{"id":"bipartite-coloring-check","version":"1.0.0","description":"Check a complete 0/1 coloring witness for graph bipartiteness and report the first certificate discrepancy.","supported_operations":["check bipartite coloring witness","validate graph two-color certificate","verify a graph is bipartite","find first invalid bipartite edge","check zero one vertex coloring","audit two-colorability witness"],"unsupported_operations":["finding a bipartition","returning an odd cycle","repairing a two-color witness"],"semantics":["colors is an index-aligned total certificate whose only admitted values are integers 0 and 1; null denotes an explicitly missing witness value.","Edges are inspected in supplied order and must join opposite values; duplicates remain significant and a self-loop conflicts.","A valid 0/1 coloring certifies bipartiteness; equivalently, a graph is bipartite exactly when it has no odd cycle.","Every verdict names Diestel Graph Theory 5th ed. (2017), sections 1.6 and 5.2.","Coverage discrepancies precede edge discrepancies; neither disconnected components nor isolated vertices receive inferred colors."],"limits":{"max_vertices":10000,"max_edges":50000},"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":["integer","null"],"minimum":0,"maximum":1}}}},"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":4,"edges":[{"from":0,"to":1},{"from":1,"to":2},{"from":2,"to":3}],"colors":[0,1,0,1]},"output":{"valid":true,"reference_version":"Diestel Graph Theory 5th ed. (2017), sections 1.6 and 5.2"}},{"input":{"vertex_count":3,"edges":[{"from":0,"to":1},{"from":1,"to":2},{"from":2,"to":0}],"colors":[0,1,0]},"output":{"valid":false,"reason":"monochromatic_edge","discrepancy":{"path":"edges[2]","index":2,"expected":"different endpoint colors","actual":0},"reference_version":"Diestel Graph Theory 5th ed. (2017), sections 1.6 and 5.2"}}],"execute_url":"/v1/tools/bipartite-coloring-check/versions/1.0.0/execute"}