Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
From MaRDI portal
Publication:412277
DOI10.1016/j.ejc.2011.09.021zbMath1239.05065OpenAlexW2090386003MaRDI QIDQ412277
Publication date: 4 May 2012
Published in: European Journal of Combinatorics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejc.2011.09.021
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)
Related Items
On approximating MIS over B1-VPG graphs*, On dominating set of some subclasses of string graphs, On quasi-planar graphs: clique-width and logical description, Coloring curves that cross a fixed curve, Quasiplanar graphs, string graphs, and the Erdős-Gallai problem, On the Size of Planarly Connected Crossing Graphs, New bounds on the maximum number of edges in \(k\)-quasi-planar graphs, Coloring intersection graphs of arc-connected sets in the plane, On the speed of algebraically defined graph classes, An algorithm for the maximum weight independent set problem on outerstring graphs, Many disjoint edges in topological graphs, Applications of a New Separator Theorem for String Graphs, Triangle-free geometric intersection graphs with no large independent sets, Two-Planar Graphs Are Quasiplanar, Unnamed Item, On-line approach to off-line coloring problems on graphs with geometric representations, Coloring non-crossing strings, Disjoint edges in complete topological graphs, Planar point sets determine many pairwise crossing segments, Outerstring Graphs are $\chi$-Bounded, Quasi-planar Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Turán-type results for partial orders and intersection graphs of convex sets
- A bipartite analogue of Dilworth's theorem
- 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
- Covering and coloring problems for relatives of intervals
- Circle orders, n-gon orders and the crossing number
- Optimal packing and covering in the plane are NP-complete
- Comparability graphs and intersection graphs
- Label placement by maximum independent set in rectangles
- Crossing families
- Some geometric applications of Dilworth's theorem
- Colouring relatives of intervals on the plane. II: Intervals and rays in two directions
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Quasi-planar graphs have a linear number of edges
- Coloring relatives of intervals on the plane. I: Chromatic number versus girth
- On geometric graphs with no \(k\) pairwise parallel edges
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Crossing number, pair-crossing number, and expansion
- On the chromatic number of intersection graphs of convex sets in the plane
- Applications of the crossing number
- Independent set of intersection graphs of convex objects in 2D
- Efficient Approximation Algorithms for Tiling and Packing Problems with Rectangles
- On a Coloring Problem.
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- Approximation schemes for covering and packing problems in image processing and VLSI
- A Separator Theorem for Planar Graphs
- Applications of a Planar Separator Theorem
- A Ramsey-Type Result for Convex Sets
- Separators for sphere-packings and nearest neighbor graphs
- Approximation algorithms for MAX–MIN tiling
- Polynomial-time approximation schemes for packing and piercing fat objects
- Intersection patterns of curves
- Intersection Graphs of Rectangles and Segments
- Some remarks on the theory of graphs
- String graphs and incomparability graphs
- Discrete and Computational Geometry
- Algorithms in real algebraic geometry
- Colouring arcwise connected sets in the plane. I
