  A graph is ambiguously k-colorable if its vertex set admits two distinct
partitions each into at most k anticliques. We give a full characterization of
the maximally ambiguously k-colorable graphs in terms of quadratic matrices. As
an application, we calculate the maximum number of edges an ambiguously
k-colorable graph can have, and characterize the extremal graphs.
