Authors:
N.R. Aravind, C.R. Subramanian
Title:
Intersection dimension and graph invariants
Source:
Discussiones Mathematicae Graph Theory
Received 05.07.2017, Revised 11.05.2018, Accepted 29.08.2018, doi: 10.7151/dmgt.2173

Abstract:
We show that the intersection dimension of graphs with respect to several hereditary properties can be bounded as a function of the maximum degree. As an interesting special case, we show that the circular dimension of a graph with maximum degree Δ is at most O({Δ}\frac{\log{Δ}}{\log\log{Δ}}). It is also shown that permutation dimension of any graph is at most Δ (\log Δ)1+o(1). We also obtain bounds on intersection dimension in terms of treewidth.
Keywords:
circular dimension, dimensional properties, forbidden-subgraph colorings

Links:
PDF