Mathematics – Combinatorics
Scientific paper
2011-09-29
Proceedings of the Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing. Congr. Num
Mathematics
Combinatorics
12 pages
Scientific paper
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.
Beyerl Jeffrey
Jamison Robert E.
No associations
LandOfFree
Interval Graphs with Containment Restrictions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Interval Graphs with Containment Restrictions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interval Graphs with Containment Restrictions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-667025