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

DOI10.1016/j.tcs.2015.03.045zbMath1326.05106DBLPjournals/tcs/HonKLLPW15OpenAlexW2049029692WikidataQ62041720 ScholiaQ62041720MaRDI QIDQ2348262

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

Publication date: 11 June 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.03.045

zbMATH Keywords

independence numbercographscategorical product of graphssplitgraphstensor capacityultimate categorical independent domination ratio

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Related Items (3)

COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB ⋮ Independence number and the number of maximum independent sets in pseudofractal scale-free web and Sierpiński gasket ⋮ Combinatorial properties of Farey graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Independent sets in direct products of vertex-transitive graphs
• The fractional version of Hedetniemi's conjecture is true
• Graph minors. III. Planar tree-width
• Homomorphisms of 3-chromatic graphs
• Graph minors. V. Excluding a planar graph
• Complement reducible graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Perfect product graphs
• A partial k-arboretum of graphs with bounded treewidth
• Modular decomposition and transitive orientation
• Independence ratios of graph powers
• Treewidth. Computations and approximations
• A survey on Hedetniemi's conjecture
• Computing the binding number of a graph
• Face covers and the genus problem for apex graphs
• Split graphs
• Algorithmic graph theory and perfect graphs
• On the ultimate independence ratio of a graph
• Asymptotic values of the Hall-ratio for graph powers
• Normal hypergraphs and the perfect graph conjecture
• Associative graph products and their independence, domination and coloring numbers
• The Ultimate Categorical Independence Ratio of Complete Multipartite Graphs
• On the Maximum Independent Set Problem in Subclasses of Planar Graphs
• The Kronecker Product of Graphs
• Independent sets in tensor graph powers
• A Linear Recognition Algorithm for Cographs
• A New Algorithm for Generating All the Maximal Independent Sets
• Approximation algorithms for NP-complete problems on planar graphs
• The Ultimate Categorical Independence Ratio of a Graph
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Partial orders of dimension 2
• The binding number of a graph and its Anderson number
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On cliques in graphs
• Hedetniemi's conjecture---a survey

This page was built for publication: On maximum independent set of categorical product and ultimate categorical ratios of graphs