2023/09/05 by Caoduro, Marco, Sebő, András · 1 citation
#05C62 #05C76 #05C85 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.2309.02062
The boxicity of a graph is the smallest dimension d allowing a representation of it as the intersection graph of a set of d-dimensional axis-parallel boxes. We present a simple general approach to determining the boxicity of a graph based on studying its ``interval-order subgraphs''. The power of the method is first tested on the boxicity of some popular graphs that have resisted previous attempts: the boxicity of the Petersen graph is 3, and more generally, that of the Kneser-graphs K(n,2) is n-2 if n≥ 5, confirming a conjecture of Caoduro and Lichev [Discrete Mathematics, Vol. 346, 5, 2023]. Since every line graph is an induced subgraph of the complement of K(n,2), the developed tools show furthermore that line graphs have only a polynomial number of edge-maximal interval-order subgraphs. This opens the way to polynomial-time algorithms for problems that are in general NP-hard: for the existence and optimization of interval-order subgraphs of line-graphs, or of interval-completions of their complement.