Independence ratios of graph powers

DOI10.1016/0012-365X(92)00480-FMaRDI QIDQ1322230zbMATH OpenOpenAlexFDO

Authors Xingxing Yu, Pavol Hell, Huishan Zhou

Publication date 5 May 1994

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(92)00480-f

zbMATH Keywords

cartesian powerscartesian productchromatic numberindependence numberindependence ratiolimit

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

Consider the limiting behaviour of the independence ratio of increasing cartesian powers of a graph. The authors observe that the limit always exists, and illustrate several situations in which the limit can be evaluated.

Recommendations

• On the ultimate independence ratio of a graph
• On the bounds for the ultimate independence ratio of a graph
• On the ultimate categorical independence ratio
• Asymptotic values of the Hall-ratio for graph powers

Cites work

• A note on the star chromatic number
• Homomorphisms of 3-chromatic graphs
• On the bounds for the ultimate independence ratio of a graph
• On the ultimate independence ratio of a graph
• The chromatic difference sequence of the Cartesian product of graphs

Cited in

(19)

• Measure preserving homomorphisms and independent sets in tensor graph powers
• A fixed box theorem for the cartesian product of graphs and metric spaces
• On the independence graph of a graph
• On the ultimate independence ratio of a graph
• On the ultimate normalized chromatic difference sequence of a graph
• Star-extremal graphs and the lexicographic product
• On the bounds for the ultimate independence ratio of a graph
• Coloring graphs by translates in the circle
• Graphs with a unique maximum independent set up to automorphisms
• Linear-time algorithms for tree root problems
• On maximum independent set of categorical product and ultimate categorical ratios of graphs
• Asymptotic values of the Hall-ratio for graph powers
• On independent domination in direct products
• Independent sets in tensor graph powers
• Bipartite density and the independence ratio
• Star chromatic numbers and products of graphs
• scientific article; zbMATH DE number 1787227 (Why is no real title available?)
• Complexity results on \(k\)-independence in some graph products
• On the independence graph of Hamming graph

This page was built for publication: Independence ratios of graph powers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1322230)