On the number of star‐shaped classes in optimal colorings of Kneser graphs

DOI10.1002/JGT.23032MaRDI QIDQ6143383zbMATH OpenOpenAlexFDO

Authors Hamid Reza Daneshpajouh

Publication date 24 January 2024

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.05605

zbMATH Keywords

chromatic numberKneser graphline graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: A family of sets is called star-shaped if all the members of the family have a point in common. The main aim of this paper is to provide a negative answer to the following question raised by James Aisenberg et al [Short proofs of the kneser-Lovasz coloring principle, Information and Computation, 261:296-310, 2018.], for the case k=2.

Recommendations

• Star coloring and tree-width of the Kneser graph \(\mathrm{KG}(n, 2)\)
• Trivial colors in colorings of Kneser graphs
• Multichromatic numbers, star chromatic numbers and Kneser graphs
• On the chromatic number of the general Kneser-graph
• Some multiple chromatic numbers of Kneser graphs

Cites work

• A certain combinatorial inequality
• A combinatorical proof of Kneser's conjecture
• A New Short Proof of Kneser's Conjecture
• Colorful subgraphs in Kneser-like graphs
• Colorings of complements of line graphs
• Hedetniemi's conjecture from the topological viewpoint
• Intersection patterns of finite sets and of convex sets
• Kneser's conjecture, chromatic number, and homotopy
• New construction of graphs with high chromatic number and small clique number
• On the chromatic number of general Kneser hypergraphs
• On the chromatic number of generalized Kneser hypergraphs
• On the neighborhood complex of \(\overrightarrow{s} \)-stable Kneser graphs
• Short proofs of the Kneser-Lovász coloring principle
• Strengthening topological colorful results for graphs
• The chromatic number of almost stable Kneser hypergraphs
• The Chromatic Number of Kneser Hypergraphs

This page was built for publication: On the number of star‐shaped classes in optimal colorings of Kneser graphs

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