characters would give an isometric embedding into a hypercube, something that is only possible for graphs that are partial cubes, and in one of their papers Graham and Pollak call a labeling that allows "✶" characters an embedding into a "squashed cube". For each position of the label strings, one can define a complete bipartite graph in which one side of the bipartition consists of the vertices labeled with 0 in that position and the other side consists of the vertices labeled with 1, omitting the vertices labeled "✶". For the complete graph, every two vertices are at distance one from each other, so every edge must belong to exactly one of these complete graphs. In this way, a labeling of this type for the complete graph corresponds to a partition of its edges into complete bipartite graphs, with the lengths of the labels corresponding to the number of graphs in the partition. Alon–Saks–Seymour conjecture Noga Alon, Michael Saks, and Paul Seymour formulated a conjecture in the early 1990s that, if true, would significantly generalize the Graham–Pollak theorem: they conjectured that, whenever a graph of chromatic number has its edges partitioned into complete bipartite subgraphs, at least subgraphs are needed. Equivalently, their conjecture states that edge-disjoint unions of complete bipartite graphs can always be colored with at most colors. The conjecture was disproved by Huang and Sudakov in 2012, who constructed families of graphs formed as edge-disjoint unions of complete bipartite graphs that require colors. Biclique partition The biclique partition problem takes as input an arbitrary undirected graph, and asks for a partition of its edges into a minimum number of complete bipartite graphs. It is NP-hard, but fixed-parameter tractable. The best approximation algorithm known for the problem has an approximation ratio of . References Algebraic graph theory