BOUNDS FOR THE BOXICITY OF MYCIELSKI GRAPHS

作者：Kamibeppu Akira^*

来源：Contributions to Discrete Mathematics, 2018, 13(1): 63-78.

• boxicity
• chromatic number
• cointerval graph
• edge clique cover number
• Mycielski graph

A box in Euclidean k-space is the Cartesian product I-1 x I-2 x . . . X I-k , where I-j is a closed interval on the real line. The boxicity of a graph G, denoted by box(G), is the minimum nonnegative integer k such that G can be isomorphic to the intersection graph of a family of boxes in Euclidean k-space.
Mycielski [11] introduced an interesting graph operation that extends a graph G to a new graph M(G), called the Mycielski graph of G. In this paper, we observe the behavior of the boxicity of Mycielski graphs. The inequality box(M(G)) >= box(G) holds for a graph G, and hence we are interested in whether the boxicity of the Mycielski graph of G is more than that of G or not. Here we give bounds for the boxicity of Mycielski graphs: for a graph G with 1 universal vertices, the inequalities box(G) + [1/2] <= box(M(G)) <= theta((G) over bar) + [1/2] + 1 hold, where theta((G) over bar) is the edge clique cover number of the complement G. Further observations determine the boxicity of the Mycielski graph M(G) if G has no universal vertices or odd universal vertices and satisfies box(G) = theta((G) over bar).
We also present relations between the Mycielski graph M(G) and its generalizations M-3(G) and M-r(G) in the context of boxicity, which will encourage us to calculate the boxicity of M(G) and M-3(G).

• 出版日期2018