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

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.

Full Text (PDF format)