View all Seminars  |  Download ICal for this event

Vertex Coloring Problem with Some Domination Properties

Series: Department Seminar

Speaker: Dr. Sayani Das Department of Mathematics Indian Institute of Technology Madras Chennai

Date/Time: Sep 23 16:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor:

Coloring and Dominating Set are two well known and well studied problems in Graph Theory. Here we consider a vertex coloring problem by imposing some domination property on it. Given a simple graph G = (V,E), in domination coloring, we need to find a vertex coloring of V such that each vertex v in V dominates some color class and each color class is dominated by some vertex v in V. The domination chromatic number of G, is the minimum number of colors used in a domination coloring of G. In minimum domination coloring we need to compute a domination coloring with minimum number of colors. We prove that, this problem is as hard as minimum vertex coloring problem. We also show that, it cannot be approximated within a factor of O(ln n), even when restricted to weakly chordal graphs. We also consider node deletion problems associated with domination coloring. Given a graph G and a positive integer q, in Minimum q-Domination Partization, it is required to find a vertex set S of minimum size such that the remaining graph is domination colorable with at most q colors. We only consider q-domination partization problem for q = 2 and q =3. We prove that Minimum 2-Domination Partization is APX-complete. It is approximable within a factor of 2 and this approximation factor is the best possible approximation factor. Then we have given the characterizations for 3-domination colorable graphs. Finally, we prove that Minimum 3-Domination Partization is APX-hard, it is equivalent to minimum odd cycle transversal and design approximation algorithm for it.

Speaker Bio:
Ph.D. Scholar, Department of Mathematics, IIT Madras.

Microsoft teams link:

Host Faculty: Dr. Arindam Khan