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

Hamid Reza Daneshpajouh

doi:10.1002/jgt.23032

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

Hamid Reza Daneshpajouh

School of Mathematical Sciences

Research output: Journal Publication › Article › peer-review

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 Aisenberg et al., for the case (Formula presented.). Do there exist (Formula presented.) -colorings of the (Formula presented.) -Kneser graphs with more than (Formula presented.) many non-star-shaped color classes?.

Original language	English
Journal	Journal of Graph Theory
DOIs	https://doi.org/10.1002/jgt.23032
Publication status	Accepted/In press - 2023

Keywords

chromatic number
Kneser graph
line graph

ASJC Scopus subject areas

Geometry and Topology
Discrete Mathematics and Combinatorics

Access to Document

10.1002/jgt.23032

Cite this

@article{a78c19641c864756ade36098377abfc8,

title = "On the number of star-shaped classes in optimal colorings of Kneser graphs",

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 Aisenberg et al., for the case (Formula presented.). Do there exist (Formula presented.) -colorings of the (Formula presented.) -Kneser graphs with more than (Formula presented.) many non-star-shaped color classes?.",

keywords = "chromatic number, Kneser graph, line graph",

author = "Daneshpajouh, {Hamid Reza}",

note = "Publisher Copyright: {\textcopyright} 2023 Wiley Periodicals LLC.",

year = "2023",

doi = "10.1002/jgt.23032",

language = "English",

journal = "Journal of Graph Theory",

issn = "0364-9024",

publisher = "Wiley-Liss Inc.",

}

TY - JOUR

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

AU - Daneshpajouh, Hamid Reza

PY - 2023

Y1 - 2023

N2 - 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 Aisenberg et al., for the case (Formula presented.). Do there exist (Formula presented.) -colorings of the (Formula presented.) -Kneser graphs with more than (Formula presented.) many non-star-shaped color classes?.

AB - 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 Aisenberg et al., for the case (Formula presented.). Do there exist (Formula presented.) -colorings of the (Formula presented.) -Kneser graphs with more than (Formula presented.) many non-star-shaped color classes?.

KW - chromatic number

KW - Kneser graph

KW - line graph

UR - http://www.scopus.com/inward/record.url?scp=85173006318&partnerID=8YFLogxK

U2 - 10.1002/jgt.23032

DO - 10.1002/jgt.23032

M3 - Article

AN - SCOPUS:85173006318

SN - 0364-9024

JO - Journal of Graph Theory

JF - Journal of Graph Theory

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this