Journal of Combinatorics

Volume 2 (2011)

Number 4

Multicolor and directed edit distance

Pages: 525 – 556

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

Authors

Maria Axenovich (Department of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

Ryan R. Martin (Department of Mathematics, Iowa State University, Ames, Ia., U.S.A.)

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.

Published 6 April 2012