Back to Search
Start Over
Coloring curves that cross a fixed curve
- Publication Year :
- 2019
-
Abstract
- We prove that for every integer $t\geq 1$, the class of intersection graphs of curves in the plane each of which crosses a fixed curve in at least one and at most $t$ points is $\chi$-bounded. This is essentially the strongest $\chi$-boundedness result one can get for this kind of graph classes. As a corollary, we prove that for any fixed integers $k\geq 2$ and $t\geq 1$, every $k$-quasi-planar topological graph on $n$ vertices with any two edges crossing at most $t$ times has $O(n\log n)$ edges.<br />Comment: Small corrections, improved presentation
- Subjects :
- Computational Geometry (cs.CG)
FOS: Computer and information sciences
050101 languages & linguistics
$k$-Quasi-planar graphs
Discrete Mathematics (cs.DM)
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
Combinatorics
Corollary
Integer
FOS: Mathematics
0202 electrical engineering, electronic engineering, information engineering
Discrete Mathematics and Combinatorics
Mathematics - Combinatorics
0501 psychology and cognitive sciences
Mathematics
000 Computer science, knowledge, general works
Mathematics::Commutative Algebra
string graphs
05 social sciences
Topological graph
Binary logarithm
Graph
Computational Theory and Mathematics
010201 computation theory & mathematics
05C62, 05C15
$χ$-Boundedness
Computer Science
Computer Science - Computational Geometry
020201 artificial intelligence & image processing
Combinatorics (math.CO)
Geometry and Topology
Computer Science - Discrete Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....f519ca60df1a6fbae060543342a83b00