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

DOI10.1137/S0895480193250162zbMATH Open0846.05052MaRDI QIDQ4881297FDOQ4881297

Authors: Thomas M. Kratzke, Douglas B. West 

Publication date: 29 July 1996

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

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
• Publication:4864784
• 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

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)

Cited In (7)

• The total interval number of a graph. I: Fundamental classes
• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• 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)