Editing Interval graph (section)

==Interval completions and pathwidth==
If <math>G</math> is an arbitrary graph, an '''interval completion''' of <math>G</math>  is an interval graph on the same vertex set that contains <math>G</math> as a subgraph. The parameterized version of interval completion (find an interval supergraph with {{mvar|k}} additional edges) is [[Parameterized complexity|fixed parameter tractable]], and moreover, is solvable in parameterized subexponential time.{{sfnp|Villanger|Heggernes|Paul|Telle|2009}}{{sfnp|Bliznets|Fomin|Pilipczuk|Pilipczuk|2014}}

The [[pathwidth]] of an interval graph is one less than the size of its maximum clique (or equivalently, one less than its chromatic number), and the pathwidth of any graph <math>G</math> is the same as the smallest pathwidth of an interval graph that contains <math>G</math> as a subgraph.{{sfnp|Bodlaender|1998}}