Star-extremal graphs and the lexicographic product

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

Xuding Zhu, Guo-Gang Gao

Publication date: 25 November 1996

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

zbMATH Keywords

circulant graphs; lexicographic product; star-chromatic number; coloring algorithms; fractional-chromatic number; star-extremal graphs

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

05C15: Coloring of graphs and hypergraphs

Related Items

The thickness and chromatic number of \(r\)-inflated graphs, Multicoloring and Mycielski construction, Coloring the Cartesian sum of graphs, Nordhaus-Gaddum inequalities for the fractional and circular chromatic numbers, Adaptable chromatic number of graph products, Circular chromatic numbers of Mycielski's graphs, Some star extremal circulant graphs, 4-colorable 6-regular toroidal graphs., On the fractional chromatic number and the lexicographic product of graphs, Asymptotic clique covering ratios of distance graphs, Star chromatic numbers of graphs, Coloring the Cartesian Sum of Graphs, Proof of a conjecture on fractional Ramsey numbers, Multi-coloring the Mycielskian 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