Proper colorability of segment intersection graphs

DOI10.1007/S10878-024-01149-3MaRDI QIDQ6571282zbMATH OpenFDO

Authors Robert D. Barish, Tetsuo Shibuya

Publication date 11 July 2024

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S10878-024-01149-3

zbMATH Keywords

\(\#P\)\(k\)-dir graphscounting exponential time hypothesis (\#ETH)exponential time hypothesis (ETH)geometric intersection graphNPproper coloringproper vertex coloringPURE-\(k\)-dir graphsSEG graphssegment intersection graphunit segment intersection graph

Mathematics Subject Classification ID

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

Cites work

• 3-coloring arrangements of line segments with 4 slopes is hard
• A better heuristic for orthogonal graph drawings
• A special planar satisfiability problem and a consequence of its NP- completeness
• Accelerated bend minimization
• Algorithms for area-efficient orthogonal drawing
• An efficient algorithm for determining the convex hull of a finite planar set
• Chromatic scheduling and frequency assignment
• Coloring intersection graphs of \(x\)-monotone curves in the plane
• Constructive generation of very hard 3-colorability instances
• Exponential Time Complexity of the Permanent and the Tutte Polynomial
• Fine-grained complexity of coloring unit disks and balls
• Frequency planning and ramifications of coloring
• Graph theory with applications
• scientific article; zbMATH DE number 4200260 (Why is no real title available?)
• scientific article; zbMATH DE number 3981198 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Intersection dimension of bipartite graphs
• Intersection graphs of curves in the plane
• Intersection graphs of segments
• Linear time transformations between combinatorial problems
• Models and solution techniques for frequency assignment problems
• On contact graphs of paths on a grid
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On intersection representations of co-planar graphs
• On the complexity of k-SAT
• Optimality program in segment and string graphs
• Proper colorability of segment intersection graphs
• Refining the hierarchies of classes of geometric intersection graphs
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
• String graphs. II: Recognizing string graphs is NP-hard
• Testing bipartiteness of geometric intersection graphs
• The clique problem in ray intersection graphs
• The complexity of computing the permanent
• The Complexity of Enumeration and Reliability Problems
• The frame dimension and the complete overlap dimension of a graph
• The node-deletion problem for hereditary properties is NP-complete
• The Ultimate Planar Convex Hull Algorithm?
• Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
• Topology of Thin Film RC Circuits
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• Unit disk graph recognition is NP-hard
• Unit disk graphs

Describes a project that uses

Uses Software

• SageMath

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6571282)