Content deleted Content added
refactor; elaborate coloring hardness |
+ref |
||
Line 17:
Every [[circle graph]], as an intersection graph of line segments (the chords of a circle), is also a string graph. Every [[chordal graph]] may be represented as a string graph: chordal graphs are intersection graphs of subtrees of trees, and one may form a string representation of a chordal graph by forming a planar embedding of the corresponding tree and replacing each subtree by a string that traces around the subtree's edges.
The [[complement graph]] of every [[comparability graph]] is also a string graph.<ref>{{harvtxt|Golumbic|Rotem|Urrutia|1983}} and {{harvtxt|Lovász|1983}}. See also {{harvtxt|Fox|Pach|2010}} and {{harvtxt|Fox|Pach|2012}}.</ref>
==Computational complexity==
Line 84:
| volume = 19
| year = 2010| s2cid = 5705145 | url = http://infoscience.epfl.ch/record/152985 }}.
*{{citation
| last1 = Fox | first1 = Jacob
| last2 = Pach | first2 = János
| doi = 10.1016/j.aim.2012.03.011
| issue = 3
| journal = Advances in Mathematics
| mr = 2921183
| pages = 1381–1401
| title = String graphs and incomparability graphs
| volume = 230
| year = 2012}}.
*{{citation
| first1 = M. | last1 = Golumbic | first2 = D. | last2 = Rotem | first3 = J. | last3 = Urrutia | author3-link = Jorge Urrutia Galicia
| |||