Revision as of 12:54, 7 June 2020 edit Citation bot (talk \| contribs) Bots 5,865,946 edits Add: issue. \| You can use this bot yourself. Report bugs here. \| Activated by SemperIocundus \| via #UCB_webform ← Previous edit		Revision as of 17:15, 12 October 2020 edit undo 130.149.14.168 (talk) →Other results: Corrected error done while citing. The statement was also false as it was. Next edit →
Line 20: {{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'') ~~edges~~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\|2015}}.</ref> ==Notes==

String graph: Difference between revisions