DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

N.R. Aravind, C.R. Subramanian

Title:

Intersection dimension and graph invariants

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-07-05, Revised: 2018-05-11, Accepted: 2018-08-29, https://doi.org/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 $\Delta$ is at most $O\left({\Delta}\frac{\log{\Delta}}{\log\log{\Delta}}\right)$. It is also shown that permutation dimension of any graph is at most $\Delta (\log \Delta)^{1+o(1)}$. We also obtain bounds on intersection dimension in terms of treewidth.

Keywords:

circular dimension, dimensional properties, forbidden-subgraph colorings

PDF
Close