Total Interval Number For Graphs With Bounded Degree
Alexander V. Kostochka, Douglas B. West · 1995
. The total interval number of an n-vertex graph with maximum degree \\Delta is at most (\\Delta + 1=\\Delta)n=2, with equality if and only if every component of the graph is K \\Delta;\\Delta . If the graph is also required to be connected, then the maximum is \\Deltan=2 +1 when \\Delta is even, but when \\Delta is odd it exceeds [\\Delta +1=(2:5\\Delta+7:7)]n=2 for infinitely many n. Given sets fS v : v 2 V g, the intersection graph of the collection of sets is the simple graph with vertex set V such that u is adjacent to v if and only if Su " S v 6= Ø. The family of sets is an intersection representation of its intersection graph. The interval graphs are the intersection graphs representable by assigning each vertex a single interval on the real line. More generally, we allow a representation f to assign each vertex a union of intervals on the real line; if G is the intersection graph of this collection, then f is a multiple-interval representation of G. Let #f(v) be the number of disjoint in...