Seminars
View all Seminars | Download ICal for this eventVertex 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:
Abstract:
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:
https://teams.microsoft.com/l/meetup-join/19%3ameeting_YzI4MTA2NGQtZDAwZS00MGU4LWI4MzktM2YyYzVjMjE0ZmYx%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%222671ab71-955e-4e4e-9268-ebb188b00539%22%7d
Host Faculty: Dr. Arindam Khan