The non-crossing graph
type: Item
instance of: scholarly article
title: The non-crossing graph
zbMATH Open document ID: 1081.05027
author: David Statter
author: Nathan Linial
author: Michael Saks
published in: The Electronic Journal of Combinatorics
publication date: 2006-01-31T00:00:00Z
full work available at URL: https://eudml.org/doc/125577
full work available at URL: v13i1n2.html
review text: 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). \]
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5002942
zbMATH Keywords: chromatic number
zbMATH Keywords: independence number
zbMATH Keywords: clique number
zbMATH Keywords: clique cover
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5002942