For a graph $H$, the $H$-free Edge Deletion problem asks whether there exist at most $k$ edges whose deletion from the input graph $G$ results in a graph without any induced copy of $H$. $H$-free Edge Completion and $H$-free Edge Editing are defined similarly where only completion (addition) of edges are allowed in the former and both completion and deletion are allowed in the latter. We completely settle the classical complexities of these problems by proving that $H$-free Edge Deletion is NP-complete if and only if $H$ is a graph with at least two edges, $H$-free Edge Completion is NP-complete if and only if $H$ is a graph with at least two nonedges, and $H$-free Edge Editing is NP-complete if and only if $H$ is a graph with at least three vertices. Our result on $H$-free Edge Editing resolves a conjecture by Alon and Stav [Theoret. Comput. Sci., 2009, pp. 4920--4927]. Additionally, we prove that these NP-complete problems cannot be solved in parameterized subexponential time, i.e., in time $2^{o(k)}\cdot |G|^{O(1)}$, unless the exponential time hypothesis fails. Furthermore, we obtain implications on the incompressibility and the inapproximability of these problems.

We consider constrained proper edge colorings of the following type: Given a positive integer j and a family $\mathcal{F}$ of connected graphs on three or more vertices, we require that the subgraph formed by the union of any j color classes has no copy of any member of $\mathcal{F}$. This generalizes some well-known types of colorings such as acyclic edge colorings, distance-2 edge colorings, low treewidth edge colorings, etc. For such a generalization of restricted colorings, we obtain an upper bound of $O(d^{\max(\theta,1)})$ on the minimum number of colors used in such a coloring. Here d refers to the maximum degree of the graph, and $\theta$ is a parameter defined by $\theta=\theta(j,\mathcal{F})=\mathit{SUP}_{H\in\mathcal{F}}\frac{(|V(H)|-2)}{(|E(H)|-j)}$, where SUP stands for the supremum. Our proof is based on probabilistic arguments. In particular, we obtain $O(d)$ upper bounds for proper edge colorings with various interesting restrictions placed on the union of color classes. For example, we obtain $O(d)$ upper bounds on edge colorings with restrictions such as (i) the union of any three color classes should be an outerplanar graph, (ii) the union of any four color classes should have treewidth at most 2, (iii) the union of any five color classes should be planar, (iv) the union of any 16 color classes should be 5-degenerate, etc. We also consider generalizations where we require simultaneously for several pairs $(j_i,\mathcal{F}_i)$ ($i=1,\dots,s$) that the union of any $j_i$ color classes has no copy of any member of $\mathcal{F}_i$ and obtain upper bounds on the corresponding chromatic indices. As a corollary, we obtain that each of the four restrictions above can be satisfied simultaneously using $O(d)$ colors. Some ways of improving the bounds are sketched. Also, if we drop the requirement that the edge coloring be proper, then an $O(d^{\theta})$ upper bound on the chromatic index is established. Further, the stated upper bounds are also bounds for the list analogues of these edge colorings.