Source author record

T. Karthick

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

7works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Coloring ( $P_5$ , kite)-free graphs

Let $P_n$ and $K_n$ denote the induced path and complete graph on $n$ vertices, respectively. The {\em kite} is the graph obtained from a $P_4$ by adding a vertex and making it adjacent to all vertices in the $P_4$ except one vertex with degree 1. A graph is ( $P_5$ , kite)-free if it has no induced subgraph isomorphic to a $P_5$ or a kite. For a graph $G$ , the chromatic number of $G$ (denoted by $χ(G)$ ) is the minimum number of colors needed to color the vertices of $G$ such that no two adjacent vertices receive the same color, and the clique number of $G$ is the size of a largest clique in $G$ . Here, we are interested in the class of ( $P_5$ , kite)-free graphs with small clique number. It is known that every ( $P_5$ ,~kite, $K_3$ )-free graph $G$ satisfies $χ(G)\leq 3$ , every ( $P_5$ ,~kite, $K_4$ )-free graph $G$ satisfies $χ(G)\leq 4$ , and that every ( $P_5$ ,~kite, $K_5$ )-free graph $G$ satisfies $χ(G)\leq 6$ . In this paper, we showed the following: $\bullet$ Every ( $P_5$ , kite, $K_6$ )-free graph $G$ satisfies $χ(G)\leq 7$ . $\bullet$ Every ( $P_5$ , kite, $K_7$ )-free graph $G$ satisfies $χ(G)\leq 9$ . We also give examples to show that the above bounds are tight.

preprint2022arXiv

Optimal chromatic bound for ( $P_2+P_3$ , $\bar{P_2+ P_3}$ )-free graphs

For a graph $G$ , let $χ(G)$ ( $ω(G)$ ) denote its chromatic (clique) number. A $P_2+P_3$ is the graph obtained by taking the disjoint union of a two-vertex path $P_2$ and a three-vertex path $P_3$ . A $\bar{P_2+P_3}$ is the complement graph of a $P_2+P_3$ . In this paper, we study the class of ( $P_2+P_3$ , $\bar{P_2+P_3}$ )-free graphs and show that every such graph $G$ with $ω(G)\geq 3$ satisfies $χ(G)\leq \max \{ω(G)+3, \lfloor\frac{3}{2} ω(G) \rfloor-1 \}$ . Moreover, the bound is tight. Indeed, for any $k\in {\mathbb N}$ and $k\geq 3$ , there is a ( $P_2+P_3$ , $\bar{P_2+P_3}$ )-free graph $G$ such that $ω(G)=k$ and $χ(G)=\max\{k+3, \lfloor\frac{3}{2} k \rfloor-1 \}$ .

preprint2021arXiv

Coloring of ( $P_5$ , $4$ -wheel)-free graphs

For a graph $G$ , $χ(G)$ $(ω(G))$ denote its chromatic (clique) number. A $P_5$ is the chordless path on five vertices, and a $4$ - $wheel$ is the graph consisting of a chordless cycle on four vertices $C_4$ plus an additional vertex adjacent to all the vertices of the $C_4$ . In this paper, we show that every ( $P_5$ , $4$ -wheel)-free graph $G$ satisfies $χ(G)\leq \frac{3}{2}ω(G)$ . Moreover, this bound is almost tight. That is, there is a class of ( $P_5$ , $4$ -wheel)-free graphs $\cal L$ such that every graph $H\in \cal L$ satisfies $χ(H)\geq\frac{10}{7}ω(H)$ . This generalizes/improves several previously known results in the literature.

preprint2016arXiv

Independent Sets in Classes Related to Chair/Fork-free Graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. MWIS is known to be $NP$ -complete in general, even under various restrictions. Let $S_{i,j,k}$ be the graph consisting of three induced paths of lengths $i, j, k$ with a common initial vertex. The complexity of the MWIS problem for $S_{1, 2, 2}$ -free graphs, and for $S_{1, 1, 3}$ -free graphs are open. In this paper, we show that the MWIS problem can solved in polynomial time for ( $S_{1, 2, 2}$ , $S_{1, 1, 3}$ , co-chair)-free graphs, by analyzing the structure of the subclasses of this class of graphs. This extends some known results in the literature.

preprint2015arXiv

Weighted Efficient Domination in Classes of $P_6$ -free Graphs

In a graph $G$ , an efficient dominating set is a subset $D$ of vertices such that $D$ is an independent set and each vertex outside $D$ has exactly one neighbor in $D$ . The Minimum Weight Efficient Dominating Set (Min-WED) problem asks for an efficient dominating set of total minimum weight in a given vertex-weighted graph; the Maximum Weight Efficient Dominating Set (Max-WED) problem is defined similarly. The Min-WED/Max-WED is known to be $NP$ -complete for $P_7$ -free graphs, and is known to be polynomial time solvable for $P_5$ -free graphs. However, the computational complexity of the Min-WED/Max-WED problem is unknown for $P_6$ -free graphs. In this paper, we show that the Min-WED/Max-WED problem can be solved in polynomial time for two subclasses of $P_6$ -free graphs, namely for ( $P_6,S_{1,1,3}$ )-free graphs, and for ( $P_6$ , bull)-free graphs.

preprint2015arXiv

Weighted Independent Sets in a Subclass of $P_6$ -free Graphs

The Maximum Weight Independent Set (MWIS) problem on graphs with vertex weights asks for a set of pairwise nonadjacent vertices of maximum total weight. The complexity of the MWIS problem for $P_6$ -free graphs is unknown. In this note, we show that the MWIS problem can be solved in time $O(n^3m)$ for ( $P_6$ , banner)-free graphs by analyzing the structure of subclasses of these class of graphs. This extends the existing results for ( $P_5$ , banner)-free graphs, and ( $P_6$ , $C_4$ )-free graphs. Here, $P_t$ denotes the chordless path on $t$ vertices, and a banner is the graph obtained from a chordless cycle on four vertices by adding a vertex that has exactly one neighbor on the cycle.

preprint2014arXiv

New polynomial case for efficient domination in $P_6$ -free graphs

In a graph $G$ , an {\it efficient dominating set} is a subset $D$ of vertices such that $D$ is an independent set and each vertex outside $D$ has exactly one neighbor in $D$ . The {\textsc{Efficient Dominating Set}} problem (EDS) asks for the existence of an efficient dominating set in a given graph $G$ . The EDS is known to be $NP$ -complete for $P_7$ -free graphs, and is known to be polynomial time solvable for $P_5$ -free graphs. However, the computational complexity of the EDS problem is unknown for $P_6$ -free graphs. In this paper, we show that the EDS problem can be solved in polynomial time for a subclass of $P_6$ -free graphs, namely ( $P_6$ , banner)-free graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

T. Karthick

Research overview

Is this your work?

7 publications

Coloring ( $P_5$ , kite)-free graphs

Optimal chromatic bound for ( $P_2+P_3$ , $\bar{P_2+ P_3}$ )-free graphs

Coloring of ( $P_5$ , $4$ -wheel)-free graphs

Independent Sets in Classes Related to Chair/Fork-free Graphs

Weighted Efficient Domination in Classes of $P_6$ -free Graphs

Weighted Independent Sets in a Subclass of $P_6$ -free Graphs

New polynomial case for efficient domination in $P_6$ -free graphs

See the researcher in context

Building this map preview

T. Karthick

Research overview

Is this your work?

7 publications

Coloring (P5P_5P5​, kite)-free graphs

Optimal chromatic bound for (P2+P3P_2+P_3P2​+P3​, P2+P3ˉ\bar{P_2+ P_3}P2​+P3​ˉ​)-free graphs

Coloring of (P5P_5P5​, 444-wheel)-free graphs

Independent Sets in Classes Related to Chair/Fork-free Graphs

Weighted Efficient Domination in Classes of P6P_6P6​-free Graphs

Weighted Independent Sets in a Subclass of P6P_6P6​-free Graphs

New polynomial case for efficient domination in P6P_6P6​-free graphs

See the researcher in context

Building this map preview

Coloring ( $P_5$ , kite)-free graphs

Optimal chromatic bound for ( $P_2+P_3$ , $\bar{P_2+ P_3}$ )-free graphs

Coloring of ( $P_5$ , $4$ -wheel)-free graphs

Weighted Efficient Domination in Classes of $P_6$ -free Graphs

Weighted Independent Sets in a Subclass of $P_6$ -free Graphs

New polynomial case for efficient domination in $P_6$ -free graphs