Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Applications of a New Separator Theorem for String Graphs
 
research article

Applications of a New Separator Theorem for String Graphs

Fox, Jacob
•
Pach, János  
2014
Combinatorics, Probability and Computing

An intersection graph of curves in the plane is called a string graph. Matousek almost completely settled a conjecture of the authors by showing that every string graph with m edges admits a vertex separator of size O(root m log m). In the present note, this bound is combined with a result of the authors, according to which every dense string graph contains a large complete balanced bipartite graph. Three applications are given concerning string graphs G with n vertices: (i) if K-t not subset of G for some t, then the chromatic number of G is at most (log n)(O(log t)); (ii) if K-t,K-t not subset of G, then G has at most t(log t)(O(1)n) edges,; and (iii) a lopsided Ramsey-type result, which shows that the Erdos-Hajnal conjecture almost holds for string graphs.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

S0963548313000412.pdf

Type

Publisher's Version

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

Size

122.9 KB

Format

Adobe PDF

Checksum (MD5)

fd000b49edde94f639a7c9c5e598c127

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés