×

Representing graphs as the intersection of cographs and threshold graphs. (English) Zbl 1467.05177

Summary: A graph \(G\) is said to be the intersection of graphs \(G_1,G_2,\ldots,G_k\) if \(V(G)=V(G_1)=V(G_2)=\cdots=V(G_k)\) and \(E(G)=E(G_1)\cap E(G_2)\cap\cdots\cap E(G_k)\). For a graph \(G, \dim_{COG}(G)\) (resp. \( \dim_{TH}(G))\) denotes the minimum number of cographs (resp. threshold graphs) whose intersection gives \(G\). We present several new bounds on these parameters for general graphs as well as some special classes of graphs. It is shown that for any graph \(G\): (a) \( \dim_{COG}(G)\leqslant\text{tw}(G)+2\), (b) \( \dim_{TH}(G)\leqslant\text{pw}(G)+1\), and (c) \( \dim_{TH}(G)\leqslant\chi(G)\cdot\text{box}(G)\), where \(\text{tw}(G), \text{pw}(G), \chi(G)\) and \(\text{box}(G)\) denote respectively the treewidth, pathwidth, chromatic number and boxicity of the graph \(G\). We also derive the exact values for these parameters for cycles and show that every forest is the intersection of two cographs. These results allow us to derive improved bounds on \(\dim_{COG}(G)\) and \(\dim_{TH}(G)\) when \(G\) belongs to some special graph classes.

MSC:

05C62 Graph representations (geometric and intersection representations, etc.)
68R10 Graph theory (including graph drawing) in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] A. Adiga, D. Bhowmick, and L. S. Chandran,Boxicity and poset dimension, SIAM Journal on Discrete Mathematics, 25 (2011), pp. 1687-1698. · Zbl 1241.05098
[2] M. O. Albertson, G. G. Chappell, H. A. Kierstead, A. K¨undgen, and R. Ramamurthi,Coloring with no 2-coloredP4’s, The Electronic Journal of Combinatorics, 11 (2004), #R26. · Zbl 1053.05045
[3] N. R. Aravind and C. R. Subramanian,Intersection dimension and graph invariants, Discussiones Mathematicae Graph Theory, 41 (2021), pp. 153-166. · Zbl 1453.05074
[4] H. L. Bodlaender,A partialk-arboretum of graphs with bounded treewidth, Theoretical Computer Science, 209 (1998), pp. 1-45. · Zbl 0912.68148
[5] A. Bohra, L. S. Chandran, and J. K. Raju,Boxicity of series-parallel graphs, Discrete Mathematics, 306 (2006), pp. 2219-2221. · Zbl 1101.05065
[6] O. V. Borodin,On acyclic colorings of planar graphs, Discrete Mathematics, 25 (1979), pp. 211-236. · Zbl 0406.05031
[7] O. V. Borodin, A. V. Kostochka, and D. R. Woodall,Acyclic colourings of planar graphs with large girth, Journal of the London Mathematical Society, 60 (1999), pp. 344-352. · Zbl 0940.05032
[8] A. Brandst¨adt, V. B. Le, and J. P. Spinrad,Graph Classes: A Survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1999. · Zbl 0919.05001
[9] Y. Bu, D. W. Cranston, M. Montassier, A. Raspaud, and W. Wang,Star coloring of sparse graphs, Journal of Graph Theory, 62 (2009), pp. 201-219. · Zbl 1179.05042
[10] L. S. Chandran and N. Sivadasan,Boxicity and treewidth, Journal of Combinatorial Theory, Series B, 97 (2007), pp. 733-744. · Zbl 1121.05091
[11] V. Chv´atal and P. L. Hammer,Aggregations of inequalities, Studies in Integer Programming, Annals of Discrete Mathematics, 1 (1977), pp. 145-162. · Zbl 0384.90091
[12] D. G. Corneil, H. Lerchs, and L. S. Burlingham,Complement reducible graphs, Discrete Applied Mathematics, 3 (1981), pp. 163-174. · Zbl 0463.05057
[13] M. B. Cozzens and R. Leibowitz,Threshold dimension of graphs, SIAM Journal on Algebraic Discrete Methods, 5 (1984), pp. 579-595. · Zbl 0717.05069
[14] M. B. Cozzens and F. S. Roberts,On dimensional properties of graphs, Graphs and Combinatorics, 5 (1989), pp. 29-46. · Zbl 0675.05054
[15] R. Diestel,Graph Theory, 4th Edition, vol. 173 of Graduate texts in mathematics, Springer, 2012.
[16] V. Dujmovi´c, P. Morin, and D. R. Wood,Layered separators in minor-closed graph classes with applications, Journal of Combinatorial Theory, Series B, 127 (2017), pp. 111-147. · Zbl 1371.05282
[17] G. Fertin, A. Raspaud, and B. Reed,Star coloring of graphs, Journal of Graph Theory, 47 (2004), pp. 163-182. · Zbl 1055.05051
[18] S. Foldes and P. L. Hammer,Split graphs having Dilworth number two, Canadian Journal of Mathematics, 29 (1977), pp. 666-672. · Zbl 0335.05130
[19] M. C. Francis and D. Jacob,The lexicographic method for the threshold cover problem.arXiv:1912.05819. · Zbl 1457.05086
[20] F. Gavril,The intersection graphs of subtrees in trees are exactly the chordal graphs, Journal of Combinatorial Theory, Series B, 16 (1974), pp. 47-56. · Zbl 0266.05101
[21] J. Gimbel and J. Neˇsetˇril,Partitions of graphs into cographs, Discrete Mathematics, 310 (2010), pp. 3437-3445. · Zbl 1209.05181
[22] M. C. Golumbic,Algorithmic graph theory and perfect graphs, vol. 57, Elsevier, 2004. · Zbl 1050.05002
[23] I. B.-A. Hartman, I. Newman, and R. Ziv,On grid intersection graphs, Discrete Mathematics, 87 (1991), pp. 41-52. · Zbl 0739.05081
[24] M. Hellmuth and N. Wieseke,On symbolic ultrametrics, cotree representations, and cograph edge decompositions and partitions, in Proceedings of the Twenty-first Annual International Computing and Combinatorics Conference, COCOON 2015, 2015, pp. 609-623. · Zbl 1468.05227
[25] H. A. Kierstead, A. K¨undgen, and C. Timmons,Star coloring bipartite planar graphs, Journal of Graph Theory, 60 (2009), pp. 1-10. · Zbl 1190.05072
[26] J. Kratochv´ıl and Z. Tuza,Intersection dimensions of graph classes, Graphs and Combinatorics, 10 (1994), pp. 159-168. · Zbl 0808.05092
[27] A. K¨undgen and C. Timmons,Star coloring planar graphs from small lists, Journal of Graph Theory, 63 (2010), pp. 324-337. · Zbl 1209.05090
[28] N. V. R. Mahadev and U. N. Peled,Threshold graphs and related topics, vol. 56, Elsevier, 1995. · Zbl 0852.05001
[29] T. Raschle and K. Simon,Recognition of graphs with threshold dimension two, in Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, STOC ’95, 1995, pp. 650-661. · Zbl 0920.05063
[30] F. S. Roberts,On the boxicity and cubicity of a graph, Recent Progresses in Combinatorics, (1969), pp. 301-310. · Zbl 0193.24301
[31] N. Robertson, D. Sanders, P. D. Seymour, and R. Thomas,The four-colour theorem, Journal of Combinatorial Theory, Series B, 70 (1997), pp. 2-44. · Zbl 0883.05056
[32] N. Robertson and P. D. Seymour,Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, 7 (1986), pp. 309-322. · Zbl 0611.05017
[33] E. R. Scheinerman,Intersection Classes and Multiple Intersection Parameters, PhD thesis, Princeton University, 1984.
[34] F. Shahrokhi,New representation results for planar graphs, in 29th European Workshop on Computational Geometry, EuroCG 2013, 2013, pp. 177-180.
[35] C. Thomassen,Interval representations of planar graphs, Journal of Combinatorial Theory, Series B, 40 (1986), pp. 9-20. · Zbl 0595.05027
[36] C. Timmons,Star coloring high girth planar graphs, The Electronic Journal of Combinatorics, 15 (2008), #R124. · Zbl 1165.05326
[37] M. Yannakakis,The complexity of the partial order dimension problem, SIAM Journal on Algebraic Discrete Methods, 3 (1982), pp. 351-358 · Zbl 0516.06001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.