BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//project/author//NONSGML v1.0//EN
CALSCALE:GREGORIAN
BEGIN:VEVENT
DTEND:20210923T120000Z
UID:1af4a6d706c83cf5eaecff7fefbd20c3-200
DTSTAMP:19700101T120016Z
DESCRIPTION:Vertex Coloring Problem with Some Domination Properties
URL;VALUE=URI:https://www.csa.iisc.ac.in/newweb/event/200/vertex-coloring-problem-with-some-domination-properties/
SUMMARY: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.
DTSTART:20210923T120000Z
END:VEVENT
END:VCALENDAR