String graph: Difference between revisions

Revision as of 20:07, 25 September 2024

Revision as of 07:14, 14 March 2025

Line 20:

==Other results==

{{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}} found that string graphs form an induced minor closed class, but not a minor closed class of graphs. Unlike for minor closed classes, where the [[Robertson–Seymour theorem]] states that there can be only finitely many [[Forbidden graph characterization|minimal forbidden minors]], Kratochvil found an infinite family of minimal forbidden induced minors for string graphs.{{sfnp|Kratochvil|1991a}}

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<sup>^{1/2}m)</supmath>''m'') vertices. It follows that the [[Biclique-free graph|biclique-free string graphs]], string graphs containing no ''K''<submath>''K_{t'',''t''}</submath> subgraph for some constant ''<math>t''</math>, have ''<math>O''(''n'')</math> edges and more strongly have [[bounded expansion|polynomial expansion]].<ref>{{harvtxt|Fox|Pach|2010}}; {{harvtxt|Dvořák|Norin|2016}}.</ref>

==Notes==