Coloring K_k-free intersection graphs of geometric objects in the plane
From MaRDI portal
Publication:412277
DOI10.1016/J.EJC.2011.09.021zbMATH Open1239.05065OpenAlexW2090386003MaRDI QIDQ412277FDOQ412277
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
Recommendations
- Coloring k k -free intersection graphs of geometric objects in the plane
- Conflict-free coloring of intersection graphs of geometric objects
- Conflict-free coloring of intersection graphs of geometric objects
- Coloring the complements of intersection graphs of geometric figures
- Colouring triangle-free intersection graphs of boxes on the plane
- scientific article; zbMATH DE number 2145236
- Coloring intersection graphs of arc-connected sets in the plane
- Coloring intersection graphs of arcwise connected sets in the plane
- On \(k\)-intersection edge colourings
- Triangle-free geometric intersection graphs with large chromatic number
Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)
Cites Work
- Title not available (Why is that?)
- Applications of a Planar Separator Theorem
- Title not available (Why is that?)
- Comparability graphs and intersection graphs
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Erdős-Hajnal-type results on intersection patterns of geometric objects
- Some remarks on the theory of graphs
- Algorithms in real algebraic geometry
- A bipartite analogue of Dilworth's theorem
- A Separator Theorem for Planar Graphs
- Separator theorems and Turán-type results for planar intersection graphs
- Intersection Graphs of Rectangles and Segments
- Approximation schemes for covering and packing problems in image processing and VLSI
- On a Coloring Problem.
- Title not available (Why is that?)
- Quasi-planar graphs have a linear number of edges
- Independent set of intersection graphs of convex objects in 2D
- Separators for sphere-packings and nearest neighbor graphs
- Optimal packing and covering in the plane are NP-complete
- Coloring relatives of intervals on the plane. I: Chromatic number versus girth
- Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane
- A Ramsey-Type Result for Convex Sets
- Covering and coloring problems for relatives of intervals
- Polynomial-time approximation schemes for packing and piercing fat objects
- On the chromatic number of intersection graphs of convex sets in the plane
- On geometric graphs with no \(k\) pairwise parallel edges
- Label placement by maximum independent set in rectangles
- Some geometric applications of Dilworth's theorem
- Colouring arcwise connected sets in the plane. I
- On the maximum number of edges in topological graphs with no four pairwise crossing edges
- Circle orders, n-gon orders and the crossing number
- Crossing families
- Colouring relatives of intervals on the plane. II: Intervals and rays in two directions
- Crossing number, pair-crossing number, and expansion
- Applications of the crossing number
- Efficient approximation algorithms for tiling and packing problems with rectangles
- Title not available (Why is that?)
- Title not available (Why is that?)
- Approximation algorithms for MAX–MIN tiling
- Title not available (Why is that?)
- Title not available (Why is that?)
- Intersection patterns of curves
- Title not available (Why is that?)
- String graphs and incomparability graphs
- Discrete and Computational Geometry
- Turán-type results for partial orders and intersection graphs of convex sets
Cited In (32)
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- Title not available (Why is that?)
- Intersection patterns of curves
- Coloring intersection graphs of arc-connected sets in the plane
- Colouring arcwise connected sets in the plane. I
- Applications of a New Separator Theorem for String Graphs
- On the speed of algebraically defined graph classes
- On the chromatic number of intersection graphs of convex sets in the plane
- Quasi-planar Graphs
- Two-Planar Graphs Are Quasiplanar
- New bounds on the maximum number of edges in \(k\)-quasi-planar graphs
- Coloring the complements of intersection graphs of geometric figures
- On-line approach to off-line coloring problems on graphs with geometric representations
- Bounds on the chromatic number of intersection graphs of sets in the plane
- Coloring non-crossing strings
- On dominating set of some subclasses of string graphs
- The discharging method in combinatorial geometry and the Pach-Sharir conjecture
- Planar point sets determine many pairwise crossing segments
- Coloring curves that cross a fixed curve
- Triangle-free geometric intersection graphs with no large independent sets
- Many disjoint edges in topological graphs
- Outerstring Graphs are $\chi$-Bounded
- Conflict-free coloring of intersection graphs of geometric objects
- The crossing Tverberg theorem
- On the Size of Planarly Connected Crossing Graphs
- On quasi-planar graphs: clique-width and logical description
- Quasiplanar graphs, string graphs, and the Erdős-Gallai problem
- On approximating MIS over B1-VPG graphs*
- Coloring k k -free intersection graphs of geometric objects in the plane
- On planar intersection graphs with forbidden subgraphs
- Disjoint edges in complete topological graphs
- An algorithm for the maximum weight independent set problem on outerstring graphs
This page was built for publication: Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q412277)
