Journal of Combinatorics
Volume 2 (2011)
Multicolor and directed edit distance
Pages: 525 – 556
The editing of a combinatorial object is the alteration of some of its elements such that the resulting object satisfies a certain fixed property. The edit problem for graphs, when the edges are added or deleted, was first studied independently by the authors and Kézdy  and by Alon and Stav . In this paper, a generalization of graph editing is considered for multicolorings of the complete graph as well as for directed graphs. Specifically, the number of edge-recolorings sufficient to be performed on any edge-colored complete graph to satisfy a given hereditary property is investigated. The theory for computing the edit distance is extended using random structures and so-called types or colored homomorphisms of graphs.
edit distance, hereditary properties, localization, split graphs, colored regularity graphs, LATEX
2010 Mathematics Subject Classification
Primary 05C35. Secondary 05C80.