Seminars

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:

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