Content deleted Content added
separators and polynomial expansion |
|||
Line 19:
==Other results==
{{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. 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|2009}}; {{harvtxt|Dvořák|Norin|2015}}.</ref>
==Notes==
Line 41 ⟶ 43:
| year = 2007
| pages = 609–617}}.
*{{citation
| last1 = Dvořák | first1 = Zdeněk | author1-link = Zdeněk Dvořák
| last2 = Norin | first2 = Sergey
| arxiv = 1504.04821
| title = Strongly sublinear separators and polynomial expansion
| year = 2015}}.
*{{citation
| first1 = G. | last1 = Ehrlich | first2 = S. | last2 = Even | first3 = R. E. | last3 = Tarjan | author3-link = Robert Tarjan
Line 51 ⟶ 59:
| doi = 10.1016/0095-8956(76)90022-8}}.
*{{citation
| last2 = Pach | first2 = János | author2-link = János Pach
| doi = 10.1017/s0963548309990459
| issue = 3
| journal = [[Combinatorics, Probability and Computing]]
| page = 371
| title = A separator theorem for string graphs and its applications
| volume = 19
| year = 2009}}.
*{{citation
| |||