Parameterized Complexity of Maximum Edge Coloring in Graphs
Abstract
The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent edges in the graph, get the same color in the proposed coloring. In the following work, we look at the other end of the spectrum where in our goal is to maximize the number of colors used for coloring the edges of the graph under some vertex specific constraints.
We deal with the MAXIMUM EDGE COLORING problem which is defined as the following –For an integer q ≥2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. The question is very well motivated by the problem of channel assignment in wireless networks. This problem is NPhard for q ≥ 2, and has been wellstudied from the point of view of approximation.
This problem has not been studied in the parameterized context before. Hence as a next step, this thesis investigates the parameterized complexity of this problem where the standard parameter is the solution size. The main focus of the work is the special case of q=2 ,i.e. MAXIMUM EDGE 2COLORING which is theoretically intricate and practically relevant in the wireless networks setting.
We first show an exponential kernel for the MAXIMUM EDGE qCOLORING problem where q is a fixed constant and q ≥ 2.We do a more specific analysis for the kernel of the MAXIMUM EDGE 2COLORING problem. The kernel obtained here is still exponential in size but is better than the kernel obtained for MAXIMUM EDGE qCOLORING problem in case of q=2.
We then show a fixed parameter tractable algorithm for the MAXIMUM EDGE 2COLORING problem with a running time of O*∗(kO(k)).We also show a fixed parameter tractable algorithm for the MAXIMUM EDGE qCOLORING problem with a running time of O∗(kO(qk) qO(k)).
The fixed parameter tractability of the dual parametrization of the MAXIMUM EDGE 2COLORING problem is established by arguing a linear vertex kernel for the problem. We also show that the MAXIMUM EDGE 2COLORING problem remains hard on graphs where the maximum degree is a constant and also on graphs without cycles of length four. In both these cases, we obtain quadratic kernels.
A closely related variant of the problem is the question of MAX EDGE{1,2}COLORING. For this problem, the vertices in the input graph may have different qε,{1.2} values and the goal is to use at least k colors for the edge coloring of the graph such that every vertex sees at most q colors, where q is either one or two. We show that the MAX EDGE{1,2}COLORING problem is W[1]hard on graphs that have no cycles of length four.
Collections
Related items
Showing items related by title, author, creator and subject.

Rainbow Colouring and Some Dimensional Problems in Graph Theory
Rajendraprasad, Deepak (20180405)This thesis touches three diﬀerent topics in graph theory, namely, rainbow colouring, product dimension and boxicity. Rainbow colouring An edge colouring of a graph is called a rainbow colouring, if every pair of vertices ... 
Rainbow Connection Number Of Graph Power And Graph Products
Arunselvan, R (20140909)The minimum number of colors required to color the edges of a graph so that any two distinct vertices are connected by at least one path in which no two edges are colored the same is called its rainbow connection number. ... 
Algorithmic and Combinatorial Questions on Some Geometric Problems on Graphs
Babu, Jasine (20180508)This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These ...