Content deleted Content added
m Open access bot: doi added to citation with #oabot. |
update to journal publication date |
||
Line 22:
{{harvtxt|Ehrlich|Even|Tarjan|1976}} showed computing the chromatic number of string graphs to be NP-hard. {{harvtxt|Kratochvil|1991a}} found that string graphs form an induced minor closed class, but not a minor closed class of graphs.
Every ''m''-edge string graph can be partitioned into two subsets, each a constant fraction the size of the whole graph, by the removal of ''O''(''m''<sup>3/4</sup>log<sup>1/2</sup>''m'') vertices. It follows that the [[Biclique-free graph|biclique-free string graphs]], string graphs containing no ''K''<sub>''t'',''t''</sub> subgraph for some constant ''t'', have ''O''(''n'') edges and more strongly have [[bounded expansion|polynomial expansion]].<ref>{{harvtxt|Fox|Pach|2010}}; {{harvtxt|Dvořák|Norin|
==Notes==
| |||