Proper colorability of segment intersection graphs
From MaRDI portal
Publication:6168981
DOI10.1007/978-3-031-22105-7_51OpenAlexW4313343193MaRDI QIDQ6168981
Robert D. Barish, Tetsuo Shibuya
Publication date: 10 August 2023
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-031-22105-7_51
NP-hardproper coloringgeometric intersection graphproper vertex coloringsegment intersection graph\(k\)-DIR graphsPURE-\(k\)-DIR graphsSEG graphsunit segment intersection graph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The clique problem in ray intersection graphs
- Coloring intersection graphs of \(x\)-monotone curves in the plane
- String graphs. II: Recognizing string graphs is NP-hard
- Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
- Intersection graphs of curves in the plane
- Chromatic scheduling and frequency assignment
- A special planar satisfiability problem and a consequence of its NP- completeness
- Intersection graphs of segments
- On intersection representations of co-planar graphs
- Algorithms for area-efficient orthogonal drawing
- A better heuristic for orthogonal graph drawings
- On contact graphs of paths on a grid
- Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
- Constructive generation of very hard 3-colorability instances
- An efficient algorithm for determining the convex hull of a finite planar set
- The frame dimension and the complete overlap dimension of a graph
- The Ultimate Planar Convex Hull Algorithm?
- Reducibility among Combinatorial Problems
- Intersection Dimension of Bipartite Graphs
- Topology of Thin Film RC Circuits
- Refining the hierarchies of classes of geometric intersection graphs
- Accelerated Bend Minimization
- Models and solution techniques for frequency assignment problems
