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

scientific article; zbMATH DE number 3741433 (Why is no real title available?)
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
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

(32)

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