Extremal Values of the Interval Number of a Graph
From MaRDI portal
Publication:3964599
DOI10.1137/0601001zbMath0499.05033OpenAlexW1983151348MaRDI QIDQ3964599
Douglas B. West, Jerrold R. Griggs
Publication date: 1980
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://authors.library.caltech.edu/12785/
Related Items
Total interval numbers of complete \(r\)-partite graphs ⋮ On an extremal problem concerning the interval number of a graph ⋮ Clique coverings of the edges of a random graph ⋮ Irredundancy in multiple interval representations ⋮ Hamiltonian circuits in interval graph generalizations ⋮ Recognizing \(d\)-interval graphs and \(d\)-track interval graphs ⋮ Interval number of special posets and random posets ⋮ A short proof of the degree bound for interval number ⋮ The total interval number of a graph ⋮ On the unit interval number of a graph ⋮ Supereulerian graphs: A survey ⋮ On the parameterized complexity of some optimization problems related to multiple-interval graphs ⋮ Three ways to cover a graph ⋮ Extremal values of the interval number of a graph. II ⋮ Extremal values of the interval number of a graph, II ⋮ Counting Interval Graphs ⋮ Edge-intersection graphs of grid paths: the bend-number ⋮ Interval numbers of powers of block graphs ⋮ On the interval number of random graphs ⋮ Scheduling split intervals with non-uniform demands ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Approximation algorithms for intersection graphs ⋮ On the bend-number of planar and outerplanar graphs ⋮ Approximating the 2-interval pattern problem ⋮ Extracting constrained 2-interval subsets in 2-interval sets ⋮ The total interval number of a tree and the Hamiltonian completion number of its line graph ⋮ Hydras: directed hypergraphs and Horn formulas ⋮ The total interval number of a graph. I: Fundamental classes ⋮ Subtree and substar intersection numbers ⋮ Optimization problems in multiple subtree graphs ⋮ On the complexity of the smallest grammar problem over fixed alphabets ⋮ On the parameterized complexity of multiple-interval graph problems ⋮ Recognizing graphs with fixed interval number is NP-complete ⋮ On the cubicity of certain graphs ⋮ The interval number of a planar graph: Three intervals suffice ⋮ Some results about the interval number of a graph ⋮ A lower bound for the interval number of a graph ⋮ Determining the interval number of a triangle-free graph ⋮ The interval number of a complete multipartite graph ⋮ Tolerance graphs ⋮ Covering and coloring problems for relatives of intervals ⋮ A note on the interval number of a graph ⋮ Irrepresentability by multiple intersection, or why the interval number is unbounded
Cites Work
- Unnamed Item
- Unnamed Item
- Extremal values of the interval number of a graph, II
- Incidence matrices and interval graphs
- Matrix characterizations of circular-arc graphs
- On double and multiple interval graphs
- Representation of a finite graph by a set of intervals on the real line
- Characterizing circular-arc graphs
- A Characterization of Comparability Graphs and of Interval Graphs
