Quasiplanar graphs, string graphs, and the Erdős-Gallai problem

DOI10.1007/978-3-031-22203-0_16arXiv2112.02378MaRDI QIDQ6117049

Publication date: 16 August 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2112.02378

zbMATH Keywords

graph coloring string graphs quasi-planar graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cites Work

Unnamed Item
Unnamed Item
Triangle-free intersection graphs of line segments with large chromatic number
Coloring $K_{k}$-free intersection graphs of geometric objects in the plane
On generalized Ramsey numbers of Erdős and Rogers
Coloring intersection graphs of $x$-monotone curves in the plane
On $K_s$-free subgraphs in $K_{s+k}$-free graphs and vertex Folkman numbers
On the maximum number of edges in quasi-planar graphs
Separator theorems and Turán-type results for planar intersection graphs
On the maximum number of edges in topological graphs with no four pairwise crossing edges
On the chromatic number of multiple interval graphs and overlap graphs
Covering and coloring polygon-circle graphs
Quasi-planar graphs have a linear number of edges
On geometric graphs with no $k$ pairwise parallel edges
$K_4$-free graphs without large induced triangle-free subgraphs
Triangle-free geometric intersection graphs with no large independent sets
Coloring curves that cross a fixed curve
A Separator Theorem for String Graphs and its Applications
Research Problems in Discrete Geometry
Generalized Nested Dissection
K^s-Free Graphs Without Large K^r-Free Subgraphs
Separators in region intersection graphs
Large K_r‐free subgraphs in K_s‐free graphs and some other Ramsey‐type problems
Bounding Ramsey numbers through large deviation inequalities
Quasi-planar Graphs
Circle graphs are quadratically χ‐bounded
Improved bounds for the Erdős-Rogers function
Outerstring Graphs are $\chi$-Bounded
Applications of a New Separator Theorem for String Graphs
The Construction of Certain Graphs
String graphs and incomparability graphs
Discrete and Computational Geometry
Colouring arcwise connected sets in the plane. I

This page was built for publication: Quasiplanar graphs, string graphs, and the Erdős-Gallai problem