Vellore Institute of Technology (VIT) is a private university located in&nbsp;Tamil Nadu, India. Founded in 1984, as Vellore Engineering College, the institution offers 20 undergraduate, 34 postgraduate, four integrated and four research programs. It has campuses in Vellore, Amravati, Bhopal and Chennai.

VIT is one of the top ranked private universities in India according to NIRF, THE and QS Rankings.&nbsp;Govt. of India has recognized&nbsp;VIT, Vellore as an&nbsp;Institution of Eminence. This has allowed VIT to take independent quality initiatives and move up in world ranking.

&nbsp;

&nbsp;

VIT University

A partition of the vertex set V(G) of a graph G into V(G) = V1∪ V2∪ ⋯ ∪ Vk is called a k-strong subcoloring if d(x, y) ≠ 2 in G for every x, y∈ Vi, 1 ≤ i≤ k where d(x, y) denotes the length of a shortest x-y path in G. The strong subchromatic number is defined as χsc(G)=min{k:Gadmits ak-strong subcoloring}. In this paper, we explore the complexity status of the StrongSubcoloring problem: for a given graph G and a positive integer k, StrongSubcoloring is to decide whether G admits a k-strong subcoloring. We prove that StrongSubcoloring is NP-complete for subcubic bipartite graphs and the problem is polynomial time solvable for trees. In addition, we prove the following dichotomy results: (i) for the class of K1,r-free split graphs, StrongSubcoloring is in P when r≤ 3 and NP-complete when r&gt; 3 and (ii) for the class of H-free graphs, StrongSubcoloring is polynomial time solvable only if H is an induced subgraph of P4; otherwise the problem is NP-complete. Next, we consider a lower bound on the strong subchromatic number. A strong set is a set S of vertices of a graph G such that for every x, y∈ S, d(x, y) = 2 in G and the cardinality of a maximum strong set in G is denoted by αs(G). Clearly, αs(G) ≤ χsc(G). We consider the complexity status of the StrongSet problem: given a graph G and a positive integer k, StrongSet asks whether G contains a strong set of cardinality k. We prove that StrongSet is NP-complete for (i) bipartite graphs and (ii) K1 , 4-free split graphs, and it is polynomial time solvable for (i) trees and (ii) P4-free graphs. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

World University root node

Mathematics

School of Advanced Sciences

Chennai Campus

Journal of Combinatorial Optimization

On the algorithmic aspects of strong subcoloring

In this paper, we introduce a graph operation, namely one-three join. We show that the graph G admits a one-three join if and only if either G is one of the basic graphs (bipartite, complement of bipartite, split graph) or G admits a constrained homogeneous set or a bipartite-join or a join. Next, we define MH as the class of all graphs generated from the induced subgraphs of an odd hole-free graph H that contains an odd anti-hole as an induced subgraph by using one-three join and co-join recursively and show that the maximum independent set problem, the maximum clique problem, the minimum coloring problem, and the minimum clique cover problem can be solved efficiently for MH.