Exactly hittable interval graphs

DOI10.46298/dmtcs.10762zbMath1546.05145MaRDI QIDQ6599815

S. M. Dhannya, N. S. Narayanaswamy, K. K. Nisha

Publication date: 6 September 2024

Published in: Discrete Mathematics and Theoretical Computer Science. DMTCS (Search for Journal in Brave)

zbMATH Keywords

interval graphsforbidden structure characterizationexact hitting sets

Mathematics Subject Classification ID

Graph theory (05C99) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Conflict-free coloring of points on a line with respect to a set of intervals
• Complexity of conflict-free colorings of graphs
• Strong conflict-free coloring for intervals
• Algorithms for four variants of the exact satisfiability problem
• Improved results on geometric hitting set problems
• A linear-time algorithm for proper interval graph recognition
• Simple linear time recognition of unit interval graphs
• Polynomial-time dualization of \(r\)-exact hypergraphs with applications in geometry
• On the stab number of rectangle intersection graphs
• The strong perfect graph theorem
• Intersection models of weakly chordal graphs
• Conflict-free coloring of unit disks
• Interval graphs and related topics
• Intersection graphs of paths in a tree
• A recognition algorithm for the intersection graphs of paths in trees
• Faster exact solutions for some NP-hard problems.
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Algorithmic graph theory and perfect graphs
• Forbidden induced subgraph characterization of circle graphs within split graphs
• Conflict-free coloring: graphs of bounded clique width and intersection graphs
• Conflict-free coloring of intersection graphs of geometric objects
• The Roberts characterization of proper and unit interval graphs
• Conflict-free coloring of points and simple regions in the plane
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The Recognition of Tolerance and Bounded Tolerance Graphs
• On partitioning interval graphs into proper interval subgraphs and related problems
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Representation of a finite graph by a set of intervals on the real line
• Exact and FPT Algorithms for Max-Conflict Free Coloring in Hypergraphs
• On The Chromatic Number of Geometric Hypergraphs
• Conflict-Free Colourings of Graphs and Hypergraphs
• Conflict-Free Coloring Made Stronger
• Characterizing path graphs by forbidden induced subgraphs
• Topics in Intersection Graph Theory
• Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
• New Results on Monotone Dualization and Generating Hypergraph Transversals
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Every planar graph is the intersection graph of segments in the plane
• Conflict-Free Coloring and its Applications
• Coloring Axis-Parallel Rectangles
• Minimally Infeasible Set-Partitioning Problems with Balanced Constraints
• Online Conflict‐Free Coloring for Intervals
• The Representation of a Graph by Set Intersections
• Computing and Combinatorics
• Perfect Resolution of Conflict-Free Colouring of Interval Hypergraphs
• LATIN 2004: Theoretical Informatics
• On rectangle intersection graphs with stab number at most two
• Intersection models and forbidden pattern characterizations for 2-thin and proper 2-thin graphs

This page was built for publication: Exactly hittable interval graphs