zbMATH — the first resource for mathematics

The non-crossing graph. (English) Zbl 1081.05027
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). \]
05C10 Planar graphs; geometric and topological aspects of graph theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C15 Coloring of graphs and hypergraphs
Full Text: EuDML EMIS