Geodesic
The non-crossing graph
The electronic journal of combinatorics, Tome 13 (2006)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Two sets are non-crossing if they are disjoint or one contains the other. The non-crossing graph ${\rm NC}_n$ is the graph whose vertex set is the set of nonempty subsets of $[n]=\{1,\ldots,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)) \le \chi({\rm NC}_n) \le n (\lceil\log_2 n\rceil-1). $$
DOI : 10.37236/1140
Classification : 05C10, 05C69, 05C15
Mots-clés : chromatic number, independence number, clique number, clique cover 
@article{10_37236_1140,
     author = {Nathan Linial and Michael Saks and David Statter},
     title = {The non-crossing graph},
     journal = {The electronic journal of combinatorics},
     year = {2006},
     volume = {13},
     doi = {10.37236/1140},
     zbl = {1081.05027},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1140/}
}
TY  - JOUR
AU  - Nathan Linial
AU  - Michael Saks
AU  - David Statter
TI  - The non-crossing graph
JO  - The electronic journal of combinatorics
PY  - 2006
VL  - 13
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1140/
DO  - 10.37236/1140
ID  - 10_37236_1140
ER  - 
%0 Journal Article
%A Nathan Linial
%A Michael Saks
%A David Statter
%T The non-crossing graph
%J The electronic journal of combinatorics
%D 2006
%V 13
%U http://geodesic.mathdoc.fr/articles/10.37236/1140/
%R 10.37236/1140
%F 10_37236_1140
Nathan Linial; Michael Saks; David Statter. The non-crossing graph. The electronic journal of combinatorics, Tome 13 (2006). doi: 10.37236/1140

Cité par Sources :