Boxicity of a Class of Split Graphs Using Words
摘要
A k-dimensional box is defined as a Cartesian product of k closed intervals on the real line \(\mathbb {R}\) . The boxicity of a graph G, denoted by \(box (G)\) , is the smallest natural number k such that G can be represented as the intersection graph of a set of k-dimensional boxes. A split graph is a graph whose vertex set can be partitioned into a clique and an independent set. It is known that the boxicity of a split graph is at most \(\min \{\frac{m}{2}, \frac{n}{2}\}\) , where m and n are the sizes of a clique and an independent set splitting the graph. Moreover, determining whether a split graph has boxicity at most three is NP-complete. In this work, we use words as a tool to determine the boxicity of a class of split graphs. We focus on graphs that are characterized by words over vertices, in which the adjacency between vertices is determined by an alternating property of letters in the word. These graphs are referred to as word-representable split graphs, a class of graphs that includes the well-known split comparability graphs. We establish that the boxicity of a word-representable split graph is at most four. In addition, we show that the boxicity of a split comparability graph is at most three.