Extremal Values of the Interval Number of a Graph

DOI10.1137/0601001zbMATH0499.05033OpenAlexW1983151348MaRDI QIDQ3964599FDOQ3964599

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)

• Determining the interval number of a triangle-free graph
• The total interval number of a graph
• Some results about the interval number of a graph
• Irrepresentability by multiple intersection, or why the interval number is unbounded
• The interval number of a planar graph: Three intervals suffice
• Tolerance graphs
• Extracting constrained 2-interval subsets in 2-interval sets
• Covering and coloring problems for relatives of intervals
• On the interval number of random graphs
• On an extremal problem concerning the interval number of a graph
• On the complexity of the smallest grammar problem over fixed alphabets
• On the unit interval number of a graph
• Clique coverings of the edges of a random graph
• Irredundancy in multiple interval representations
• Extremal values of the interval number of a graph, II
• A lower bound for the interval number of a graph
• Total interval numbers of complete \(r\)-partite graphs
• Recognizing unit multiple interval graphs is hard
• A note on the interval number of a graph
• On the cubicity of certain graphs
• The interval number of a complete multipartite graph
• Recognizing graphs with fixed interval number is NP-complete
• Supereulerian graphs: A survey
• A short proof of the degree bound for interval number
• Subtree and substar intersection numbers
• Counting Interval Graphs
• Optimization problems in multiple subtree graphs
• The total interval number of a graph. I: Fundamental classes
• On the parameterized complexity of some optimization problems related to multiple-interval graphs
• Edge-intersection graphs of grid paths: the bend-number
• Interval number of special posets and random posets
• Extremal values of the interval number of a graph. II
• On the parameterized complexity of multiple-interval graph problems
• Hydras: directed hypergraphs and Horn formulas
• 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
• Scheduling split intervals with non-uniform demands
• Approximating the 2-interval pattern problem
• Approximation algorithms for intersection graphs
• Hamiltonian circuits in interval graph generalizations
• The total interval number of a tree and the Hamiltonian completion number of its line graph

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)