On maximum independent set of categorical product and ultimate categorical ratios of graphs

Wing Kai Hon, Ton Kloks, Ching Hao Liu, Hsiang Hsuan Liu, Sheung Hung Poon, Yue Li Wang

Research output: Journal PublicationArticlepeer-review

2 Citations (Scopus)

Abstract

We first present polynomial algorithms to compute the independence number of the categorical product for two cographs or two splitgraphs, respectively. Then we prove that computing the maximum independent set of the categorical product of a planar graph of maximum degree three and a K4 is NP-complete. The ultimate categorical independence ratio of a graph G is defined as limk→∞α(Gk)/nk. The ultimate categorical independence ratio can be computed in polynomial time for cographs, splitgraphs, permutation graphs, interval graphs and graphs of bounded treewidth. Also, we present an O*(3n/3)-time exact, exponential algorithm for the ultimate categorical independence ratio of general graphs. We further present a PTAS for the ultimate categorical independence ratio of planar graphs. Lastly, we show that the ultimate categorical independent domination ratio for complete multipartite graphs is zero, except when the graph is complete bipartite with color classes of equal size (in which case it is 1/2).

Original languageEnglish
Pages (from-to)81-95
Number of pages15
JournalTheoretical Computer Science
Volume588
DOIs
Publication statusPublished - 11 Jul 2015
Externally publishedYes

Keywords

  • Categorical product of graphs
  • Cographs
  • Independence number
  • Splitgraphs
  • Tensor capacity
  • Ultimate categorical independent domination ratio

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'On maximum independent set of categorical product and ultimate categorical ratios of graphs'. Together they form a unique fingerprint.

Cite this