The interval number of a planar graph: Three intervals suffice

DOI10.1016/0095-8956(83)90050-3MaRDI QIDQ786830zbMATH OpenOpenAlexWikidataFDO

Authors Edward Scheinerman, Douglas B. West

Publication date 1983

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(83)90050-3

zbMATH Keywords

interval graphinterval numberinterval representationplanar graphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99)

Cites work

• Construction of ternary H_v-groups and ternary P-hyperoperations.
• Extremal Values of the Interval Number of a Graph
• Extremal values of the interval number of a graph, II
• scientific article; zbMATH DE number 3741433 (Why is no real title available?)
• scientific article; zbMATH DE number 3547322 (Why is no real title available?)
• On double and multiple interval graphs
• Recognizing graphs with fixed interval number is NP-complete
• The interval number of a complete multipartite graph

Cited in

(28)

• On the parameterized complexity of multiple-interval graph problems
• Localized and compact data-structure for comparability graphs
• On star and caterpillar arboricity
• A note on the interval number of a graph
• Interval representations of planar graphs
• On an extremal problem concerning the interval number of a graph
• Irredundancy in multiple interval representations
• The total interval number of a graph
• On the unit interval number of a graph
• On grid intersection graphs
• Representations of graphs and networks (coding, layouts and embeddings)
• Interval numbers of powers of block graphs
• Scheduling split intervals with non-uniform demands
• The interval number of a planar graph is at most three
• Caterpillar arboricity of planar graphs
• Edge-intersection graphs of grid paths: the bend-number
• Distance Labeling for Permutation Graphs
• On the interval number of special graphs
• Fast diameter computation within split graphs
• Representation of Planar Hypergraphs by Contacts of Triangles
• On interval representations of graphs
• Some new results on bar visibility of digraphs
• Subtree and substar intersection numbers
• Generalizing Roberts' characterization of unit interval graphs
• Recognizing graphs with fixed interval number is NP-complete
• Tree loop graphs
• Three ways to cover a graph
• On the interval number of random graphs

This page was built for publication: The interval number of a planar graph: Three intervals suffice

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