  In this paper we introduce and study a new problem named \emph{min-max edge
$q$-coloring} which is motivated by applications in wireless mesh networks. The
input of the problem consists of an undirected graph and an integer $q$. The
goal is to color the edges of the graph with as many colors as possible such
that: (a) any vertex is incident to at most $q$ different colors, and (b) the
maximum size of a color group (i.e. set of edges identically colored) is
minimized. We show the following results: 1. Min-max edge $q$-coloring is
NP-hard, for any $q \ge 2$. 2. A polynomial time exact algorithm for min-max
edge $q$-coloring on trees. 3. Exact formulas of the optimal solution for
cliques and almost tight bounds for bicliques and hypergraphs. 4. A non-trivial
lower bound of the optimal solution with respect to the average degree of the
graph. 5. An approximation algorithm for planar graphs.
