Geodesic
INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs
Commentationes Mathematicae Universitatis Carolinae, Tome 31 (1990) no. 1, pp. 85-93 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

Classification : 05C85, 05C99, 68Q25, 68R10 
@article{CMUC_1990_31_1_a10,
     author = {Kratochv{\'\i}l, Jan and Ne\v{s}et\v{r}il, Jaroslav},
     title = {INDEPENDENT {SET} and {CLIQUE} problems in intersection-defined classes of graphs},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {85--93},
     year = {1990},
     volume = {31},
     number = {1},
     mrnumber = {1056173},
     zbl = {0727.05056},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1990_31_1_a10/}
}
TY  - JOUR
AU  - Kratochvíl, Jan
AU  - Nešetřil, Jaroslav
TI  - INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs
JO  - Commentationes Mathematicae Universitatis Carolinae
PY  - 1990
SP  - 85
EP  - 93
VL  - 31
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/CMUC_1990_31_1_a10/
LA  - en
ID  - CMUC_1990_31_1_a10
ER  - 
%0 Journal Article
%A Kratochvíl, Jan
%A Nešetřil, Jaroslav
%T INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs
%J Commentationes Mathematicae Universitatis Carolinae
%D 1990
%P 85-93
%V 31
%N 1
%U http://geodesic.mathdoc.fr/item/CMUC_1990_31_1_a10/
%G en
%F CMUC_1990_31_1_a10
Kratochvíl, Jan; Nešetřil, Jaroslav. INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 31 (1990) no. 1, pp. 85-93. http://geodesic.mathdoc.fr/item/CMUC_1990_31_1_a10/

[EET] Ehrlich G., Even S., Tarjan R. E.: Intersection graphs of curves in the plane. J. Combin. Th. Ser. B 21 (1976), 8-20. | MR | Zbl

[FPP] de Fraysseix H., Pach J., Pollack R.: Small sets supporting Fáry embeddings of planar graphs. STOC 1988.

[Gav] Gavril F.: Algorithms for a maximum clique and maximum independent set of a circle graph. Networks 4 (1973), 261-273. | MR

[GJ] Garey M. R., Johnson D. S.: Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, 1979. | MR | Zbl

[Kra1] Kratochvíl J.: String graphs I. The number of critical nonstring graphs is infinite. (to appear in J. Combin. Th. Ser. B). | MR

[Kra2] Kratochvíl J.: String graphs II. Recognizing string graphs in NP-hard. (to appear in J. Combin. Th. Ser. B). | MR

[KGK] Kratochvíl J., Goljan M., Kučera P.: String graphs. Rozpravy československé akademie věd, ŘMPV 96, No. 3, Academia, Prague, 1986. | MR

[KM] Kratochvíl J., Matoušek J.: Intersections graphs of segments. submitted.

[KM2] Kratochvíl J., Matoušek J.: NP-hardness results for intersection graphs. Comment. Math. Univ. Carolinae 30 (1989), 761-773. | MR

[MP] Middendorf M., Pfeiffer F.: Max clique problem in classes of string graphs. preprint Univ. Bonn (1988). | MR

[S] Sinden F. W.: Topology of thin film RC circuits. Bell System Tech. J. (1966), 1639-1662. | Zbl

[V] Valiant L. G.: Universality considerations in VLSI circuits. IEEE Trans. Comput. 30 (1981), 135-140. | MR | Zbl