Recognizing graphs with fixed interval number is NP-complete

Recommendations

On interval representations of graphs
The Total Interval Number of a Graph II: Trees and Complexity
Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
Interval graph representation with given interval and intersection lengths
Interval graph representation with given interval and intersection lengths

Cites work

Covering edges by cliques with regard to keyword conflicts and intersection graphs
Extremal Values of the Interval Number of a Graph
Extremal values of the interval number of a graph. II
scientific article; zbMATH DE number 3741433 (Why is no real title available?)
On double and multiple interval graphs
Polynomial Complete Consecutive Information Retrieval Problems
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
The interval number of a complete multipartite graph
The interval number of a planar graph: Three intervals suffice
Two-Processor Scheduling with Start-Times and Deadlines

Cited in

(34)

On the parameterized complexity of multiple-interval graph problems
On an extremal problem concerning the interval number of a graph
Irredundancy in multiple interval representations
On the unit interval number of a graph
Representations of graphs and networks (coding, layouts and embeddings)
Interval numbers of powers of block graphs
On the computational complexity of 2-interval pattern matching problems
Precedence thinness in graphs
The interval number of a planar graph is at most three
Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review
The maximum clique problem in multiple interval graphs
Recognizing d-interval graphs and d-track interval graphs
Edge-intersection graphs of grid paths: the bend-number
Extracting constrained 2-interval subsets in 2-interval sets
On local structures of cubicity 2 graphs
Recognizing \(d\)-interval graphs and \(d\)-track interval graphs
Interval graph representation with given interval and intersection lengths
Interval graph representation with given interval and intersection lengths
Fast diameter computation within split graphs
Optimization problems in multiple subtree graphs
An interval chaos insight to iterative decomposition method for Rossler differential equation by considering stable uncertain coefficients
On interval representations of graphs
On the parameterized complexity of some optimization problems related to multiple-interval graphs
A graph-theoretic barcode ordering model for linked-reads
Recognizing unit multiple interval graphs is hard
Some new results on bar visibility of digraphs
Recognizing unit multiple intervals is hard
Generalizing Roberts' characterization of unit interval graphs
The interval number of a planar graph: Three intervals suffice
Using fractional primal-dual to schedule split intervals with demands
Tree loop graphs
Three ways to cover a graph
Recognizing tough graphs is NP-hard
On the interval number of random graphs

This page was built for publication: Recognizing graphs with fixed interval number is NP-complete

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