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

DOI10.1002/JGT.23032arXiv2201.05605OpenAlexW4387013725MaRDI QIDQ6143383FDOQ6143383

Authors: Hamid Reza Daneshpajouh 

Publication date: 24 January 2024

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

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.

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

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

zbMATH Keywords

chromatic numberKneser graphline graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Cites Work

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