Proper colorability of segment intersection graphs

DOI10.1007/978-3-031-22105-7_51MaRDI QIDQ6168981zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

\(k\)-DIR graphsgeometric intersection graphNP-hardproper coloringproper vertex coloringPURE-\(k\)-DIR graphsSEG graphssegment intersection graphunit segment intersection graph

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx)

Recommendations

• Properly colored connectivity of graphs
• scientific article; zbMATH DE number 6667033
• Coloring intersection graphs of arcwise connected sets in the plane
• Coloring intersection graphs of arc-connected sets in the plane
• On proper-path colorings in graphs
• Conflict-free coloring of intersection graphs
• Conflict-free coloring of intersection graphs
• scientific article; zbMATH DE number 3885934
• Coloring the complements of intersection graphs of geometric figures
• Coloring hypergraphs with bounded cardinalities of edge intersections

Cites work

• 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
• 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?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• Intersection dimension of bipartite graphs
• Intersection graphs of curves in the plane
• Intersection graphs of segments
• Models and solution techniques for frequency assignment problems
• On contact graphs of paths on a grid
• On intersection representations of co-planar graphs
• Reducibility among combinatorial problems
• 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
• The clique problem in ray intersection graphs
• The frame dimension and the complete overlap dimension of a graph
• The Ultimate Planar Convex Hull Algorithm?
• Topology of Thin Film RC Circuits
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete

Cited in

(3)

• Choice of the control variables of an isolated intersection by graph colouring
• Proper colorability of segment intersection graphs
• Recognition and proper coloring of unit segment intersection 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 Q6168981)