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: |