arXiv:1705.04395v1 [math.CO] 11 May 2017

Unit Incomparability Dimension and Clique
Cover Width in Graphs
Farhad Shahrokhi
Department of Computer Science and Engineering, UNT
farhad@cs.unt.edu
Abstract
For a clique cover C in the undirected graph G, the clique cover
graph of C is the graph obtained by contracting the vertices of each
clique in C into a single vertex. The clique cover width of G, denoted by CCW (G), is the minimum value of the bandwidth of all
clique cover graphs in G. Any G with CCW (G) = 1 is known to be
an incomparability graph, and hence is called, a unit incomparability graph. We introduced the unit incomparability dimension of G,
denoted by U dim(G), to be the smallest integer d so that there are
unit incomparability graphs Hi with V (Hi ) = V (G), i = 1, 2, ..., d, so
that E(G) = ∩di=1 E(Gi ). We prove a decomposition theorem establishing the inequality U dim(G) ≤ CCW (G). Specifically, given any
G, there are unit incomparability graphs H1 , H2 , ..., HCC(W ) with
V (Hi ) = V (G) so that and E(G) = ∩CCW
i=1 E(Hi ). In addition, Hi is
co-bipartite, for i = 1, 2, ..., CCW (G) − 1. Furthermore, we observe
that CCW (G) ≥ s(G)/2 − 1, where s(G) is the number of leaves in a
largest induced star of G , and use Ramsey Theory to give an upper
bound on s(G), when G is represented as an intersection graph using
our decomposition theorem. Finally, when G is an incomparability
graph we prove that CCW (G) ≤ s(G) − 1.

1

Introduction and Summary

Throughout this paper, G = (V (G), E(G)) denotes a graph on n vertices.
G is assumed to be undirected, unless stated otherwise. The complement of
G is denoted by Ḡ. A set C of vertex disjoint cliques in G is a clique cover, if
every vertex in V is, precisely, in one clique of C. Let L = {v0 , v2 , ..., vn−1 }
be a linear ordering of vertices in G. The width of L, denoted by W (L),
is maxvi vj ∈E(G) |j − i|. The bandwidth of G [2], [3], denoted by BW (G), is
the smallest width of all linear orderings of V (G). The bandwidth problem
is well studied and has intimate connections to other important concepts

including graph separation [4], [1], [7]. Unfortunately, computing the bandwidth is N P − hard, even if G is a tree [11].
In [15] we introduced the clique cover width problem which is a generalization of the bandwidth problem. For C a clique cover of G, let the clique
cover graph of C, denoted by G(C), be the graph obtained from C by contracting the vertices in each clique to one vertex in G. Thus V (G(C)) = C,
and E(G(C)) = {XY |X, Y ∈ C, there is xy ∈ E(G) with x ∈ X, and, y ∈
Y }. The clique cover width of G, denoted by CCW (G), is the minimum
value of BW (G(C)), where the minimum is taken over all clique covers C
of G. Note that CCW (G) ≤ BW (G), since {{x}|x ∈ V (G)} is a trivial
clique cover in G containing cliques that have only one vertex. We highly
suspect that the problem of computing CCW(G) is N P hard, due to the
connection to the bandwidth prob- lem. Let C be a clique cover in G.
Throughout this paper, we will write C = {C0 , C1 , ..., Ct } to indicate that
C is an ordered set of cliques. For a clique cover C = {C0 , C1 , ..., Ct }, in G,
let the width C, denoted by W (C), denote max{|j − i| |Ci Cj ∈ E(C(G))}.
Observe that, W (C) = max{|j − i||xy ∈ E(G), x ∈ Ci , y ∈ Cj , Ci , Cj ∈ C}.
An crucial tool for the design of a divide and conquer algorithm is
separation. The planar separation [12] asserts that any n vertex planar
graph can be separated √
into two subgraphs, each having at most 2n/3
vertices, by removing O( n) vertices. The key application of the clique
cover width is in the derivation of separation theorems in graphs, where
separation can be defined for other types measures [14], instead of just the
number of vertices. For instance, given a clique cover C in G, can G be
separated by removing a *small* number of cliques in C so that each the
two remaining subgraph of G can be covered by at most α|C| cliques from
C, where α < 1 is a constant [14, 16]?
Any (strict) partially ordered set (S, <) has a directed acyclic graph Ĝ
associated with it in a natural way: V (G) = S, and ab ∈ E(G) if and only
if a < b. The comparability graph associated with (S, <) is the undirected
graph which is obtained by dropping the orientation on edges of Ĝ [6, 21].
The complement of a comparability graph is an incomparability graph.
Any graph G with CCW (G) = 1 is known to be an incomparability graph [15], and hence we call such a G a unit incomparability graph.
Clearly, any co-bipartite graph, or the complement of a bipartite graph is
a unit comparability graph. In addition, it is easy to verify that any unit
interval graph is also a unit incomparability graph. Thus, the class of unit
incomparability graphs is relatively large.
Let d ≥ 1, and for i = 1, 2, ..., d let Hi be a graph with V (Hi ) = V , and
let G be a graph with V (G) = V and E(G) = ∩di=1 E(Gi ). Then, we say

that G is the intersection graph of H1 , H2 , ..., Hd , and write G = ∩di=1 Hi
[18]. Let the incomparability dimension of G, denoted by Idim(G), be
the smallest integer d so that there are d incomparability graphs whose
intersection graph is G. Similarly, let the unit incomparability dimension
of G, denoted by U dim(G), be the smallest integer d so that there are
d unit incomparability graphs whose intersection is G. In this paper we
focus on the connection between the the clique cover width and the unit
incomparability dimension of a graph. Our work gives rise to a new way
of representing any graph as the intersection graph of unit incomparability
graphs.
Recall that Boxicity, and Cubicity of a graph, denoted Box(G) and
Cub(G) respectively, are the smallest integer d so that G is the intersection
graph of d interval graphs, or unit interval graphs, respectively [13]. Recent
work [18, 19] has elevated the importance of the Boxicity and the Cubicity,
by improving the upper bounds, and by linking these concepts to other important graph parameters including treewidth [4], Poset dimension [21], and
crossing numbers [17]. Clearly, Idim(G) ≤ U dim(G), Box(G) ≤ Cub(G),
Idim(G) ≤ Box(G), and U dim(G) ≤ Cub(G).
While Cubicity and Boxicity are related to unit incomparability dimension, and while the results in [18, 19] are extremely valuable, these results
do not imply, or even address the concepts and results presented here, particularly, due to the focus of our work on the pivoting concept of the clique
cover width.
In Section two we prove a decomposition theorem that establishes the
inequality U dim(G) ≤ CCW (G), for any graph G. Furthermore, we observe that CCW (G) ≥ (s(G)/2) − 1, where s(G) is the largest number of
leaves in an induced star in G, and use Ramsey Theory to give an upper
bound on s(G), when G is represented as an intersection graph using our
decomposition theorem. In Section three we study the clique cover width
problem in incomparability graphs, and prove that s(G) − 1 ≥ CCW (G),
when G is an incomparability graph. The results give rise to polynomial
time algorithms for the construction of the appropriate structures.
Remark. In work in progress, the author has improved the upper
bound on U dim(G) (in the decomposition theorem) to O(log(CCW (G)).
This drastically improves all upper bounds presented here.

2

Main Results

Now we prove the decomposition result.

Theorem 2.1 (Decomposition Theorem) Let C = {C0 , C1 , ..., Ct } be a
a clique cover in G. Then, there are W (C) unit incomparability graphs
H1 , H2 , ..., HW (C) whose intersection is G. Specifically, Hi is a co-bipartite
graph, for i = 1, 2..., W (C) − 1. Moreover, the constructions can be done
in polynomial time.
Proof. For i = 1, 2, ..., W (C) − 1, we define a graph H̄i on the vertex
set V (G) and the edge set
E(H̄i ) = {xy ∈ E(Ḡ)|x ∈ Cl , y ∈ Ck , |k − l| = i},
and prove that H̄i is a bipartite graph. For i = 1, 2, ..., W (C) − 1, let odd(i)
and even(i) denote the set of all integers 0 ≤ j ≤ t, so that j = a.i + r, r ≤
i−1, where a ≥ 0 is odd, or even, respectively, and note that odd(i)∪even(i)
is a partition of {0, 1, 2, ..., t}. Next, for i = 1, 2, ..., W (C) − 1, let V1 =
{x ∈ Cj |j ∈ odd(i)} and V2 = {x ∈ Cj |j ∈ even(i)}, and note V1 ∪ V2 is a
partition of V (G) so that any edge in E(H̄i ) has one end point in V1 and
the other end point in ∈ V2 . Therefore, for i = 1, 2, ..., W (C) − 1, H̄i is
bipartite, and consequently, Hi is co-bipartite. Next, let H̄W (C) be a graph
on the vertex set V (G) and the edge set
E(H̄W (C) ) = {xy ∈ E(Ḡ)|x ∈ Cl , y ∈ Ck , |l − k| ≥ W (C)}.
Let xy ∈ E(H̄), then y ∈ Cl and x ∈ Ck with |l − k| ≥ W (C). Now orient
xy from x to y, if l ≥ k + W (C), otherwise, orient xy from y to x. It
is easy to verify that this orientation is transitive, and hence H̄W (C) is a
comparability graph. Consequently, HW (C) is an incomparability graph.
We need to show CCW (HW (C) ) = 1. First, observe that any consecutive
subset cliques of in C of cardinality at at most W (C) is a clique in HW (C) .
Next, let t = a.W (C) + r, r ≤ W (C) − 1. For i = 0, 1, ..., a − 1, let Si be
the set of all W (C) consecutive cliques in C starting at i.W (C) + 1 and
ending at (i + 1)W (C). Define Sa to be the set of r consecutive cliques
in C, starting at Ca.W (C + 1 and ending in Ct . It is easy to verify that
S = {S0 , S2 , ..., Sa } is a clique cover in HW (C) with W (S) = 1, and thus
CCW (HW (C) ) = 1. ✷
Remark 2.1 If G is a clique, then CCW (G) = 0, where, U dim(G) =
1. In addition, if G is disconnected, then CCW (G) and U dim(G) equal
to the maximum values of these parameters, respectively, taken over all
components of G.
A Simple consequence of Theorem 2.1 is the following.
Corollary 2.1 CCW (G) ≥ U dim(G), for any connected graph G which
is not a clique.

In light of Theorem 2.1 , one may want to have estimates for CCW (G).
Let s(G) denote the number of leaves for a largest induced star in G. When
|V (G)|2, we define s(G) = 1.
Observation 2.1 Let C = {C0 , C1 ..., Ck } be a clique cover in G, then,
W (C) ≥ ⌈ s(G)
2 ⌉ − 1.
Proof. Let S be an induced star with center r and s(G) leaves. Then,
r ∈ Ci for some 0 ≤ i ≤ t. Note that no two leaves in S can be in
the same clique of C, and hence there must be an edge rx ∈ E(S) with
x ∈ Cj for some 0 ≤ j ≤ t so that |j − i| ≥ ⌈ s(G)
2 ⌉ − 1. Consequently,
s(G)
W (C) ≥ ⌈ 2 ⌉ − 1. ✷
Ideally, one would like to have a converse for Theorem 2.1, where the
clique cover width of G can be estimated using the clique cover widths for
the factor graphs. Unfortunately, we have not been to derive a general
result that can used effectively. In addition, Observation 2.1 poses the
problem of finding an upper bound for CCW (G) in terms of s(G), only.
Unfortunately this is also impossible. For instance, take the n × n planar
gird G, then s(G) = 4, but CCW (G) is unbounded. (We omit the details.)
Nonetheless, one may pose the related question of finding an upper bound
for s(G) in G = ∩i=1 Hi , using s(Hi), i = 1, 2, ..., d.
For integers, n1 , n2 ..., nc let R(n1 , n2 , ..., nc ) denote the general Ramsey
number. Thus for any t ≥ R(n1 , n2 , ..., nc ), if the edges of Kt are colored
with c different colors, then for some 1 ≤ i ≤ c, we always get a complete
subgraph of Kt , on ni vertices, whose edges are all colored with color i.
Theorem 2.2 Let G = ∩di=1 Hi , then s(G) < R(s(H1 )+1, s(H2 )+1, ..., s(Hd )+
1).
Proof. Assume to the contrary that s(G) ≥ R(s(H1 ) + 1, s(H2 ) +
1, ..., s(Hd ) + 1), and let S be an induced star in G rooted at r with s(G)
leaves. Note that S = ∩di=1 Si , where for i = 1, 2, ..., d, Si is an induced
subgraph of Hi with V (Si ) = V (S). Now let H be a complete graph on
the vertex set V (H) = V (S){r}. Thus, the vertex set of H is precisely
the set of leaves in S. Now for i = 1, 2, ..., d, and for any ab ∈ E(H),
assign color i to ab, if and only if, ab ∈
/ E(Si ). Since|V (H)| = s(G) ≥
R(s(H1 ), s(H2 ), ..., s(Hd )), there must be a monochromatic complete subgraph of H on color i, with least s(Hi ) + 1 vertices, for some 1 ≤ i ≤ d. Let
Wi denote the set of vertices for this complete sub- graph, and note that
our coloring policy implies that Wi is an independent set of vertices in Hi
. Thus Wi ∪ {r} is an induced star in Hi with at least s(Hi ) + 1 > s(Hi )
leaves which is a contradiction. ✷
Corollary 2.2 For any G, s(G) < R(

3, 3, ..., 3
| {z }

CCW (G)−1 times

, 4).

Proof. By Theorem 2.1 , there are CCW (G) unit incomparability
graphs H1 , H2 , ..., HW (C) whose intersection is G. Observe, that s(Hi ) ≤ 2,
since Hi is co-bipartite for i = 1, 2, ..., CCW (G) − 1, and, s(HCCW (G) ) ≤ 3,
since HCCW (G) is a unit incomparability graph. Now apply Theorem 2.2.
✷

3

Clique Cover Width in Incomparability Graphs

Theorem 3.1 Let G be an incomparability graph, then there is a clique
cover C = {C0 , C1 , ..., Ck } so that s(G)−1 ≥ W (C) ≥ ⌈ s(G)
2 ⌉−1. Moreover,
if graph Ĝ, or the transitive orientation of Ḡ, is given in its adjacency list
form, then C and W (C) can be computed in O(|V (G)| + |E(G)|) time.
Proof. Let C = {C0 , C1 , ..., Ck } be a greedy clique cover in G, where
k + 1 is the size of largest independent set in G. Thus, C1 is the set
of all sources in the Ĝ, C2 is the set of all forces that are obtained after
removal of C1 , etc. The lower bound for W (C) follow from Observation 2.1.
For the upper bound, let e = ab ∈ E(G) with a ∈ Ci , b ∈ Cj , j > i so that
W (C) = |j − i|. Now let xj = b, then for t = i, i + 1, ..., j − 1 there is xt ∈ Ct
so that xt xt+1 ∈ E(Ĝ). It follows that for t, p = i, i + 1, ..., j, p > t, we have
tp ∈ E(Ĝ) and thus tp ∈
/ E(G). We conclude that the induced graph on
a, xi , xi+1 , ..., xj is a star in G, with center a, having j − i + 1 = W (C) + 1
leaves. Consequently, s(G) ≥ j − i + 1 ≥ W (C) + 1. To finish the proof,
and for the algorithm one can apply topological ordering to graph Ĝ to
compute C and W (C) in linear time. ✷
Corollary 3.1 G be an incomparability graph then, CCW (G) can be approximated within a factor of two, in O(|V | + |E|) time.
Corollary 3.2 Let G be a incomparability graph, then U dim(G) ≤ s(G)−
1.
Remark 3.1 Let G be a co-bipartite which is not a clique. Then, S(G) = 2
and CCW (G) = 1, and hence the upper bound in Theorem 3.1 is tight.
Let G be graph consisting of 3 cliques C1 , C2 , C3 , in that order, each
on 4 vertices, with xi ∈ Ci , i = 1, 2, 3 and additional edges, x1 x2 and x2 x3
. Then, s(G) = 3, and CCW (G) = 1, and hence the lower bound in
Observation 2.1 is tight.

References
[1] J. Böttcher, K. P. Pruessmannb, A. Taraz, A. Würfel Bandwidth,
treewidth, separators, expansion, and universality, Electronic Notes
in Discrete Mathematics, 31(20), 2008, 91-96.

[2] P.Z. Chinn, J. Chvatalov , A. K. Dewdney, N.E. Gibb , Bandwidth
problem for graphs and matrices- A Survey, Journal of Graph Theory,
6(3),2006, 223-254
[3] J. Diaz, J. Petit, M. Serna A survey of graph layout problems, ACM
Computing Surveys (CSUR) 34(3), 2002, 313 - 356.
[4] H.L. Bodlaender , A Tourist Guide through Treewidth. Acta Cybern.
11(1-2), 1993, 1-22.
[5] Golumbic, M.; Rotem, D.; Urrutia, J. (1983), ”Comparability graphs
and intersection graphs”, Discrete Mathematics 43 (1): 3746.
[6] Golumbic, Martin Charles (1980). Algorithmic Graph Theory and Perfect Graphs. Academic Press.
[7] Ellis J.A, Sudborough I.H., Turner J.S., The vertex separation and
search number of a graph, Information and Computation, 113(1), 1994,
50-79.
[8] B. Dushnik, E. W. Miller, Partially ordered Sets, American Journal of
Mathematics 63(3), 1941, 600-610.
[9] J. Fox, J. Pach, A separator theorem for string graphs and its applications, Combinatorics, Probability and Computing 19(2010), 371-390.
[10] J. Fox and J. Pach, String graphs and incomparability graphs, Advances in Mathematics, 2009.
[11] M.R. Garey and D.J. Johnson, Computers and Intractability: A Guide
to the Theory of NP-Completeness, Freeman, San Francisco, CA, 1978.
[12] R.J. Lipton, R.E. Tarjan, A separator theorem for planar graphs,
SIAM Journal on Applied Mathematics 36, 1979, 177-189.
[13] F. Roberts. Recent Progresses in Combinatorics, chapter On the boxicity and cubicity of a graph, pages 301310. Academic Press, New York,
1969.
[14] F. Shahrokhi, A New Separation Theorem with Geometric Applications, Proceedings of EuroCG2010, 2010, 253-256.
[15] F. Shahrokhi, On the clique cover width problem, Congressus Numerantium 205 (2010), 97-103.
[16] F. Shahrokhi, in preparation.

[17] Shahrokhi, F., Sýkora, O., Székely, L.A., and Vrt́o, I., Crossing Number Problems: Bounds and Applications, in Intuitive Geometry eds.
I. Bárány and K. Böröczky, Bolyai Society Mathematical Studies 6,
1997, 179-206.
[18] L. Sunil Chandran and Naveen Sivadasan. Boxicity and treewidth.
Journal of Combinatorial Theory, Series B, 97(5):733744, September
2007.
[19] Abhijin Adiga, L. Sunil Chandran, Rogers Mathew: Cubicity, Degeneracy, and Crossing Number. FSTTCS 2011: 176-190.
[20] W.T. Trotter, New perspectives on interval orders and interval graphs,
in Surveys in Combinatorics, Cambridge Univ. Press, 1977, 237-286.
[21] W.T. Trotter, Combinatorics and partially ordered sets: Dimension
theory, Johns Hopkins series in the mathematical sciences, The Johns
Hopkins University Press, 1992.

