Interval Graphs with Containment Restrictions

MaRDI QIDQ3615962zbMATH OpenFDO

Authors Jeffery J. Beyerl, Robert E. Jamison

Publication date 24 March 2009

Full work available at URL https://arxiv.org/abs/1109.6675

zbMATH Keywords

proper interval graphsinterval graphminimal forbidden subgraphimproper interval graphs

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Abstract: An interval graph is proper iff it has a representation in which no interval contains another. Fred Roberts characterized the proper interval graphs as those containing no induced star $K_{1,3}$. Proskurowski and Telle have studied $q$-proper graphs, which are interval graphs having a representation in which no interval is properly contained in more than $q$ other intervals. Like Roberts they found that their classes of graphs where characterized, each by a single minimal forbidden subgraph. This paper initiates the study of $p$-improper interval graphs where no interval contains more than $p$ other intervals. This paper will focus on a special case of $p$-improper interval graphs for which the minimal forbidden subgraphs are readily described. Even in this case, it is apparent that a very wide variety of minimal forbidden subgraphs are possible.

Recommendations

• Interval graphs with side (and size) constraints
• On interval representations of graphs
• scientific article; zbMATH DE number 1933220
• scientific article; zbMATH DE number 4027515
• Classes of interval graphs under expanding length restrictions
• scientific article; zbMATH DE number 1375584
• Interval-regular graphs
• Bounded representations of interval and proper interval graphs
• Interval-like graphs and digraphs
• scientific article; zbMATH DE number 1923007

Cited in

(10)

• Towards a comprehensive theory of conflict-tolerance graphs
• Minimum proper interval graphs
• A characterization of k-trees that are interval p-graphs
• Bigraph impropriety
• Improper interval graphs and the corresponding minimal forbidden interval subgraphs
• Realizing Interval Graphs with Size and Distance Constraints
• scientific article; zbMATH DE number 1375584 (Why is no real title available?)
• A characterization of 2-tree proper interval 3-graphs
• End vertices in containment interval graphs
• Stability of critical p-improper interval graphs

This page was built for publication: Interval Graphs with Containment Restrictions

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