In a partially fixed two-colour edge coloring of a complete graph, complete all unassigned edges independently and fairly. For a fixed clique with unassigned edges, its conditional probability of becoming monochromatic is zero if both colours already occur; if a colour is fixed and no conflicting colour occurs; and if none is fixed. Sum these conditional probabilities over the cliques to obtain a computable conditional expectation. Fix each next edge to a colour that does not increase this conditional expectation, yielding a deterministic minimization construction.
Articles by others on the same topic
There are currently no matching articles.