Star-extremal graphs and the lexicographic product

DOI10.1016/0012-365X(94)00311-6zbMath0852.05046OpenAlexW2123110140MaRDI QIDQ1917490

Guo-Gang Gao, Xuding Zhu

Publication date: 25 November 1996

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0012-365x(94)00311-6

zbMATH Keywords

circulant graphslexicographic productstar-chromatic numbercoloring algorithmsfractional-chromatic numberstar-extremal graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items (20)

Asymptotic clique covering ratios of distance graphs ⋮ Some star extremal circulant graphs ⋮ 4-colorable 6-regular toroidal graphs. ⋮ The fractional version of Hedetniemi's conjecture is true ⋮ Multicoloring and Mycielski construction ⋮ Proof of a conjecture on fractional Ramsey numbers ⋮ Multi-coloring the Mycielskian of graphs ⋮ On Motzkin's problem in the circle group ⋮ The thickness and chromatic number of \(r\)-inflated graphs ⋮ A note on Hedetniemi's conjecture, Stahl's conjecture and the Poljak-Rödl function ⋮ Coloring graphs by translates in the circle ⋮ Coloring the Cartesian sum of graphs ⋮ On the independence ratio of distance graphs ⋮ Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers ⋮ Star chromatic numbers of graphs ⋮ Adaptable chromatic number of graph products ⋮ Counterexamples to Hedetniemi's conjecture with large fractional chromatic numbers ⋮ On the fractional chromatic number and the lexicographic product of graphs ⋮ Circular chromatic numbers of Mycielski's graphs ⋮ Coloring the Cartesian Sum of Graphs

Cites Work

• Unnamed Item
• Homomorphisms of 3-chromatic graphs
• On multiplicative graphs and the product conjecture
• Triangle-free regular graphs
• n-tuple colorings and associated graphs
• Independence ratios of graph powers
• On the ultimate independence ratio of a graph
• A note on the star chromatic number
• Star chromatic number
• Star chromatic numbers and products of graphs
• The star chromatic number of a graph
• Acyclic graph coloring and the complexity of the star chromatic number

This page was built for publication: Star-extremal graphs and the lexicographic product