Editing Interval graph (section)

=== Proper interval graphs ===
{{main|Proper interval graph}}
[[Proper interval graph]]s are interval graphs that have an interval representation in which no interval [[Subset|properly contains]] any other interval; [[unit interval graph]]s are the interval graphs that have an interval representation in which each interval has unit length. A unit interval representation without repeated intervals is necessarily a proper interval representation. Not every proper interval representation is a unit interval representation, but every proper interval graph is a unit interval graph, and vice versa.<ref>{{harvtxt|Roberts|1969}}; {{harvtxt|Gardi|2007}}</ref> Every proper interval graph is a [[claw-free graph]]; conversely, the proper interval graphs are exactly the claw-free interval graphs. However, there exist claw-free graphs that are not interval graphs.{{sfnp|Faudree|Flandrin|Ryjáček|1997|p=89}}

An interval graph is called <math>q</math>-proper if there is a representation in which no interval is contained by more than <math>q</math> others. This notion extends the idea of proper interval graphs such that a 0-proper interval graph is a proper interval graph.{{sfnp|Proskurowski|Telle|1999}}
An interval graph is called <math>p</math>-improper if there is a representation in which no interval contains more than <math>p</math> others. This notion extends the idea of proper interval graphs such that a 0-improper interval graph is a proper interval graph.{{sfnp|Beyerl|Jamison|2008}}
An interval graph is <math>k</math>-nested if there is no chain of length <math>k+1</math> of intervals nested in each other. This is a generalization of proper interval graphs as 1-nested interval graphs are exactly proper interval graphs.{{sfnp|Klavík|Otachi|Šejnoha|2019}}