Proper colorability of segment intersection graphs

DOI10.1007/s10878-024-01149-3MaRDI QIDQ6571282

Tetsuo Shibuya, Robert D. Barish

Publication date: 11 July 2024

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

zbMATH Keywords

proper coloringNPgeometric intersection graphproper vertex coloringsegment intersection graph\(\#P\)exponential time hypothesis (ETH)SEG graphsunit segment intersection graph\(k\)-dir graphscounting exponential time hypothesis (\#ETH)PURE-\(k\)-dir graphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Discrete geometry (52C99) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Cites Work

• Unnamed Item
• 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
• The complexity of computing the permanent
• String graphs. II: Recognizing string graphs is NP-hard
• The node-deletion problem for hereditary properties is NP-complete
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Unit disk graphs
• 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
• Unit disk graph recognition is NP-hard
• Algorithms for area-efficient orthogonal drawing
• A better heuristic for orthogonal graph drawings
• 3-coloring arrangements of line segments with 4 slopes is hard
• 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?
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• The Complexity of Enumeration and Reliability Problems
• Linear time transformations between combinatorial problems
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Frequency planning and ramifications of coloring
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Testing bipartiteness of geometric intersection graphs
• Intersection Dimension of Bipartite Graphs
• Topology of Thin Film RC Circuits
• Refining the hierarchies of classes of geometric intersection graphs
• Accelerated Bend Minimization
• Optimality program in segment and string graphs
• Models and solution techniques for frequency assignment problems
• On the complexity of \(k\)-SAT
• Proper colorability of segment intersection graphs

This page was built for publication: Proper colorability of segment intersection graphs