NP-hardness results for intersection graphs

Jan Kratochvíl; Jiří Matoušek

Displaying similar documents to “NP-hardness results for intersection graphs”

INDEPENDENT SET and CLIQUE problems in intersection-defined classes of graphs

Jan Kratochvíl, Jaroslav Nešetřil (1990)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Two results concerning string graphs

Jan Kratochvíl (1988)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

Graphs of low chordality.

Chandran, L.Sunil, Lozin, Vadim V., Subramanian, C.R. (2005)

Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]

Similarity:

The crossing numbers of join products of paths with graphs of order four

Marián Klešč, Stefan Schrötter (2011)

Discussiones Mathematicae Graph Theory

Similarity:

Kulli and Muddebihal [V.R. Kulli, M.H. Muddebihal, Characterization of join graphs with crossing number zero, Far East J. Appl. Math. 5 (2001) 87-97] gave the characterization of all pairs of graphs which join product is planar graph. The crossing number cr(G) of a graph G is the minimal number of crossings over all drawings of G in the plane. There are only few results concerning crossing numbers of graphs obtained as join product of two graphs. In the paper, the exact values of crossing...