On double and multiple interval graphs

DOI10.1002/JGT.3190030302MaRDI QIDQ3206997zbMATH OpenOpenAlexFDO

Authors William T. Trotter, Frank Harary

Publication date 1979

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/jgt.3190030302

zbMATH Keywords

treeinterval numberinterval graphcomplete bipartite graphscheduling problemsallocation problems

Mathematics Subject Classification ID

Graph theory (05C99)

Cites work

• A Characterization of Comparability Graphs and of Interval Graphs
• Incidence matrices and interval graphs

Cited in

(48)

• Counting Interval Graphs
• On the chromatic number of multiple interval graphs and overlap graphs
• Scheduling split intervals with non-uniform demands
• \(k\)-separator chordal graphs: leafage and subfamilies
• On the interval number of random graphs
• Recognizing graphs with fixed interval number is NP-complete
• The interval number of a planar graph is at most three
• Irrepresentability by multiple intersection, or why the interval number is unbounded
• On an extremal problem concerning the interval number of a graph
• Extremal values of the interval number of a graph. II
• Interval numbers of powers of block graphs
• A note on the interval number of a graph
• Cyclic arrangements with minimum modulo \(m\) winding numbers
• Complexity issues in color-preserving graph embeddings
• Tolerance graphs
• Gallai-type results for multiple boxes and forests
• Extremal Values of the Interval Number of a Graph
• Total interval numbers of complete \(r\)-partite graphs
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Determining DNA sequence similarity using maximum independent set algorithms for interval graphs
• A characterization of Robert's inequality for boxicity
• Approximating the 2-interval pattern problem
• Extracting constrained 2-interval subsets in 2-interval sets
• Extremal values of the interval number of a graph, II
• Splitting plane graphs to outerplanarity
• Some results about the interval number of a graph
• The interval number of a complete multipartite graph
• The interval number of a planar graph: Three intervals suffice
• On the unit interval number of a graph
• Three ways to cover a graph
• Edge-intersection graphs of grid paths: the bend-number
• Splitting plane graphs to outerplanarity
• Recognizing unit multiple interval graphs is hard
• Clique tree generalization and new subclasses of chordal graphs
• The maximum clique problem in multiple interval graphs
• Hamiltonian circuits in interval graph generalizations
• A lower bound for the interval number of a graph
• Determining the interval number of a triangle-free graph
• Irredundancy in multiple interval representations
• Tree loop graphs
• Interview with Douglas West
• Hydras: directed hypergraphs and Horn formulas
• The total interval number of a tree and the Hamiltonian completion number of its line graph
• Recognizing d-interval graphs and d-track interval graphs
• On the interval number of special graphs
• Covering and coloring problems for relatives of intervals
• Precedence thinness in graphs
• Representations of graphs and networks (coding, layouts and embeddings)

This page was built for publication: On double and multiple interval graphs

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