Content deleted Content added
→References: bad bibcode for arxiv version, not journal version |
→Other results: move link end |
||
Line 22:
{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed computing the [[chromatic number]] of string graphs to be NP-hard.{{sfnp|Ehrlich|Even|Tarjan|1976}} {{harvtxt|Kratochvil|1991a}} observed that [[Graph minor#Induced minors|induced minors]] of string graphs are also string graphs. Induced minors are obtained from a given graph by contracting edges and deleting vertices; unlike the more general form of graph minor they do not allow deleting edges. For graph minors, the [[Robertson–Seymour theorem]] states that any graph property closed under minors has finitely many [[Forbidden graph characterization|minimal forbidden minors]]. However, this does not hold for induced minors, and Kratochvil found an infinite family of minimal forbidden induced minors for string graphs.{{sfnp|Kratochvil|1991a}}
Analogously to the [[planar separator theorem]], every <math>m</math>-edge string graph can be partitioned into two subsets, each a constant fraction the size of the whole graph, by the removal of <math>O(m^{3/4}\log^{1/2}m)</math> vertices. It follows that the [[Biclique-free graph|biclique-free]] string graphs
==Notes==
| |||