Intersection Dimension and Graph Invariants

Aravind, N.R. ; Subramanian, C.R.

Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 1, pp. 153-166

Résumé

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(Δ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.

Détail

Keywords: circular dimension, dimensional properties, forbidden-subgraph colorings

Bibliographie

[1] A. Adiga, D. Bhowmick and L.S. Chandran, Boxicity and poset dimension, SIAM J. Discrete Math. 25 (2011) 1687–1698. doi: 10.1137/100786290

[2] M.O. Albertson, G.G. Chappell, H.A. Kierstead, A. Kündgen and R. Ramamurthi, Coloring with no 2-colored P 4 's, Electron. J. Combin. 11 (2004) #R26.

[3] N. Alon, C. McDiarmid and B.A. Reed, Acyclic coloring of graphs, Random Structures Algorithms 2 (1991) 277–288. doi: 10.1002/rsa.3240020303

[4] N.R. Aravind and C.R. Subramanian, Bounds on edge colorings with restrictions on the union of color classes, SIAM J. Discrete Math. 24 (2010) 841–852. doi: 10.1137/080733917

[5] N.R. Aravind and C.R. Subramanian, Bounds on vertex colorings with restrictions on the union of color classes, J. Graph Theory 66 (2011) 213–234. doi: 10.1002/jgt.20501

[6] N.R. Aravind and C.R. Subramanian, Forbidden subgraph colorings and the oriented chromatic number, European J. Combin. 34 (2013) 620–631. doi: 10.1016/j.ejc.2011.09.045

[7] A. Brandstädt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey (SIAM Monographs on Discrete Mathematics and Applications, 1999). doi: 10.1137/1.9780898719796

[8] L.S. Chandran, M.C. Francis and N. Sivadasan, Boxicity and maximum degree, J. Combin. Theory Ser. B 98 (2008) 443–445. doi: 10.1016/j.jctb.2007.08.002

[9] L.S. Chandran and N. Sivadasan, Boxicity and treewidth, J. Combin. Theory Ser. B 97 (2007) 733–744. doi: 10.1016/j.jctb.2006.12.004

[10] M.B. Cozzens and F.S. Roberts, On dimensional properties of graphs, Graphs Combin. 5 (1989) 29–46. doi: 10.1007/BF01788656

[11] L. Esperet, Boxicity of graphs with bounded degree, European J. Combin. 30 (2009) 1277–1280. doi: 10.1016/j.ejc.2008.10.003

[12] R.B. Feinberg, The circular dimension of a graph, Discrete Math. 25 (1979) 27–31.

[13] G. Fertin, A. Raspaud and B.A. Reed, Star coloring of graphs, J. Graph Theory 47 (2004) 163–182. doi: 10.1002/jgt.20029

[14] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs (Annals of Mathematics 57, Elsevier, 2004).

[15] I.B.-A. Hartman, I. Newman and R. Ziv, On grid intersection graphs, Discrete Math. 87 (1991) 41–52. doi: 10.1016/0012-365X(91)90069-E

[16] H. Hind, M. Molloy and B. Reed, Colouring a graph frugally, Combinatorica 17 (1997) 469–482.

[17] J. Kratochvil and Zs. Tuza, Intersection dimension of graph classes, Graphs Combin. 10 (1994) 159–168.

[18] B. Mohar and S. Špacapan, Coloring parameters for graphs on surfaces, Electron. Notes Discrete Math. 31 (2008) 281–286. doi: 10.1016/j.endm.2008.06.057

[19] M. Molloy and B. Reed, Asymptotically optimal frugal coloring, J. Combin. Theory Ser. B 100 (2010) 226–246. doi: 10.1016/j.jctb.2009.07.002

[20] J. Nešetřil and P. Ossona de Mendez, Colorings and homomorphisms of minor closed classes, in: Discrete and Computational Geometry, The Goodman-Pollack Festschrift, B. Aronov, S. Basu, J. Pach and M. Sharir (Ed(s)), (Springer-Verlag, 2003) 651–664.

[21] J.B. Shearer, A note on circular dimension, Discrete Math. 29 (1980) 103. doi: 10.1016/0012-365X(90)90290-X

[22] E.R. Scheinerman, Intersection Classes and Multiple Intersection Parameters (Princeton University, 1984).

[23] C. Thomassen, Interval representations of planar graphs, J. Combin. Theory Ser. B 40 (1986) 9–20. doi: 10.1016/0095-8956(86)90061-4