The Total Interval Number of a Graph II: Trees and Complexity

DOI10.1137/S0895480193250162MaRDI QIDQ4881297zbMATH OpenFDO

Authors Thomas M. Kratzke, Douglas B. West

Publication date 29 July 1996

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895480193250162

zbMATH Keywords

treesinterval graphsNP-completenesscharacterizationintersection graphinterval numberline graphslinear-time algorithmtrailsextremal treesmultiple-interval representationtotal interval numberAigner-Andreae bound

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38)

Recommendations

• The total interval number of a tree and the Hamiltonian completion number of its line graph
• On Cayley's formula for counting trees in nested interval graphs
• On the enumeration of interval graphs
• The total interval number of a graph. I: Fundamental classes
• On the domatic number of interval graphs
• scientific article; zbMATH DE number 846956
• scientific article; zbMATH DE number 1011262
• scientific article; zbMATH DE number 5671249
• Proper interval graph extention problems of the complements of trees
• The interval number of a complete multipartite graph

Cited in

(8)

• The total interval number of a graph. I: Fundamental classes
• scientific article; zbMATH DE number 5671249 (Why is no real title available?)
• Recognizing graphs with fixed interval number is NP-complete
• Proper interval graph extention problems of the complements of trees
• Total interval numbers of complete \(r\)-partite graphs
• The total interval number of a graph. III: Tree-like graphs.
• scientific article; zbMATH DE number 894698 (Why is no real title available?)
• Hydras: directed hypergraphs and Horn formulas

This page was built for publication: The Total Interval Number of a Graph II: Trees and Complexity

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