The non-crossing graph (Q813926): Difference between revisions
From MaRDI portal
Removed claims |
Changed an Item |
||
Property / author | |||
Property / author: Nathan Linial / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Michael E. Saks / rank | |||
Normal rank |
Revision as of 09:43, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The non-crossing graph |
scientific article |
Statements
The non-crossing graph (English)
0 references
31 January 2006
0 references
Summary: Two sets are non-crossing if they are disjoint or one contains the other. The non-crossing graph NC\(_n\) is the graph whose vertex set is the set of nonempty subsets of \([n]=\{1,\dots,n\}\) with an edge between any two non-crossing sets. Various facts, some new and some already known, concerning the chromatic number, fractional chromatic number, independence number, clique number and clique cover number of this graph are presented. For the chromatic number of this graph we show: \[ n(\log_e n -\Theta(1)) \leq \chi(\text{NC}_n) \leq n (\lceil\log_2 n\rceil -1). \]
0 references
chromatic number
0 references
independence number
0 references
clique number
0 references
clique cover
0 references