Extremal Values of the Interval Number of a Graph

DOI10.1137/0601001MaRDI QIDQ3964599zbMATH OpenOpenAlexFDO

Authors Douglas B. West, J. 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/

zbMATH Keywords

interval graphsmaximum degreeinterval numbercollection of finite closed intervals

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35)

Cites work

• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 3307331 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• Characterizing circular-arc graphs
• 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

Cited in

(43)

• Counting Interval Graphs
• Supereulerian graphs: A survey
• The total interval number of a graph
• The total interval number of a graph. I: Fundamental classes
• Scheduling split intervals with non-uniform demands
• Optimization problems in multiple subtree graphs
• On the interval number of random graphs
• Recognizing graphs with fixed interval number is NP-complete
• Subtree and substar intersection numbers
• Irrepresentability by multiple intersection, or why the interval number is unbounded
• On an extremal problem concerning the interval number of a graph
• A short proof of the degree bound for interval number
• 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
• Clique coverings of the edges of a random graph
• Tolerance graphs
• Interval number of special posets and random posets
• Total interval numbers of complete \(r\)-partite graphs
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• On the complexity of the smallest grammar problem over fixed alphabets
• On the parameterized complexity of multiple-interval graph problems
• 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
• Approximation algorithms for intersection graphs
• 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
• Recognizing unit multiple interval graphs is hard
• 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
• 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 cubicity of certain graphs
• Covering and coloring problems for relatives of intervals
• Representations of graphs and networks (coding, layouts and embeddings)

This page was built for publication: Extremal Values of the Interval Number of a Graph

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