View all Seminars  |  Download ICal for this event

Improved Approximation Bounds On Maximum Edge q-coloring Of Dense Graphs

Series: M.Tech (Research) Colloquium

Speaker: Talha Hashim M.Tech (Research) student Dept. of C.S.A

Date/Time: Jan 31 11:00:00

Location: CSA Seminar Hall (Room No. 254, First Floor)

Faculty Advisor: Prof. Sunil Chandran Leela

The {it anti-Ramsey number} $ar(G,H)$ with {it input graph} $G$ and {it pattern graph} $H$, is the maximum positive integer $k$ such that there exists an edge coloring of $G$ using $k$ colors, in which there are no {it rainbow} subgraphs isomorphic to $H$ in $G$. ($H$ is {it rainbow} if all its edges get distinct colors). The concept of {it anti-Ramsey number} was introduced by Erd os, Simanovitz, and S'os in 1973. Thereafter several researchers investigated this concept in the {it combinatorial} setting. The cases where pattern graph $H$ is a complete graph $K_r$, a path $P_r$ or a star $K_{1,r}$ for a fixed positive integer $r$, are well studied. Recently, Feng et al. revisited the {it anti-Ramsey} problem for the pattern graph $K_{1,t}$ (for $t ge 3$) purely from an {it algorithmic} point of view, due to its applications in {it interference modeling} of {it wireless networks}. They posed it as an optimization problem, the emph {maximum edge $q$-coloring problem.} For a graph $G$ and an integer $qgeq 2$, an edge $q$-coloring of $G$ is an assignment of colors to edges of $G$, such that edges incident on a vertex span at most $q$ distinct colors. The {it maximum edge} $q$-coloring problem seeks to {it maximize} the number of colors in an edge $q$-coloring of the graph $G$. Note that the {it optimum value} of the edge $q$-coloring problem of $G$ equals $ar(G,K_{1,q+1})$. We study $ar(G,K_{1,t})$, the {it anti-Ramsey number} of stars, for each fixed integer $tgeq 3$, both from {it combinatorial} and {it algorithmic} point of view. The first of our main results, presents an upper bound for $ar(G,K_{1,q+1})$, in terms of number of vertices and the minimum degree of $G$. The second one improves this result for the case of triangle free input graphs. For a positive integer $t$, let $H_t$ denote a subgraph of $G$ with maximum number of possible edges and maximum degree $t$. From an observation of Erd"os, Simanovitz, and S'os, we get: $|E(H_{q-1})| + 1leq ar(G,K_{1,q+1}) leq |E(H_{q})|$. For instance, when $q=2$, the subgraph $E(H_{q-1})$ refers to a maximum matching. It looks like $|E(H_{q-1})|$ is the most natural parameter associated with the anti-ramsey number $ar(G,K_{1,q+1})$ and the approximation algorithms for the maximum edge coloring problem proceed usually by first computing the $H_{q-1}$, then coloring all its edges with different colors and by giving one (sometimes more than one) extra colors to the remaining edges. The approximation guarantee of these algorithms usually depend on upper bounds for $ar(G,K_{1,q+1})$ in terms of $|E(H_{q-1})|$. Our third main result presents an upper bound for $ar(G,K_{1,q+1})$ in terms of $|E(H_{q-1})|$. All our results have algorithmic consequences. For some large special classes of graphs, such as $d$-regular graphs, where $dgeq 4$, our results can be used to prove a better approximation guarantee for the sub-factor based algorithm (Algorithm~ref{alg:feng}). We also show that all our bounds are almost tight. Results for the case $q=2$ were done earlier by Chandran et al cite{chandran18}. In this thesis, we extend it further for each fixed integer $q > 2$.

Speaker Bio:

Host Faculty: