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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Boxicity of a Class of Split Graphs Using Words

  • Khyodeno Mozhui,
  • Tithi Dwary

摘要

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.