A box in Euclidean k-space is the Cartesian product of k closed intervals on the real line. The boxicity of a graph G, denoted by box(G), is the mini- mum nonnegative integer k such that G can be isomorphic to the intersection graph of a family of boxes in Euclidean k-space. The concept of boxicity of graphs was introduced by F. S. Roberts (1969) and has an application to a problem of niche overlap in ecology for example.
In this talk, as one of research topics on boxicity, we introduce the following lower bound for boxicity given by Adiga et al. (2013) :, where the symbol denotes the complement of G andis an interval supergraph of G on V (G) with the minimum number of edges among all such interval supergraphs of G. We review the above lower bound in the context of fractional graph theory and present a fractional analogue related to boxicity. We show that the inequalities hold.
Akira Kamibeppu,日本Shimane University副教授。2004年于Tokyo University of Science获得学士学位,2006、2009年于University of Tsukuba 获得硕士和博士学位。2009-2010年在Yokohama National University任Assistant Professor,2013年在Yamaguchi University任Assistant Professor,2010年在Shimane University 任副教授。主要从事图论、线性规划等方面的研究。