Contents Online

# Journal of Combinatorics

## Volume 2 (2011)

### Number 4

### Multicolor and directed edit distance

Pages: 525 – 556

DOI: http://dx.doi.org/10.4310/JOC.2011.v2.n4.a4

#### Authors

#### Abstract

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 [4] and by Alon and Stav [3]. 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.

#### Keywords

edit distance, hereditary properties, localization, split graphs, colored regularity graphs, LATEX

#### 2010 Mathematics Subject Classification

Primary 05C35. Secondary 05C80.