The 4-girth-thickness of the complete multipartite graph

Christian Rubio-Montiel

Abstract


The g-girth-thickness θ(g, G) of a graph G is the smallest number of planar subgraphs of girth at least g whose union is G. In this paper, we calculate the 4-girth-thickness θ(4, G) of the complete m-partite graph G when each part has an even number of vertices.


Keywords


thickness, planar decomposition, complete multipartite graph, girth

Full Text:

PDF

DOI: http://dx.doi.org/10.5614/ejgta.2019.7.1.14

References

A. Aggarwal, M. Klawe and P. Shor, Multilayer grid embeddings for VLSI, Algorithmica 6 (1) (1991), 129–151.

V.B. Alekseev and V.S. Goncˇakov, The thickness of an arbitrary complete graph, Mat. Sb. (N.S.) 101 (143) (1976), no. 2, 212–230.

G. Araujo-Pardo, F.E. Contreras-Mendoza, S.J. Murillo-Garc ́ıa, A.B. Ramos-Tort and C. Rubio-Montiel, Complete colorings of planar graphs, Discrete Appl. Math. 255 (2019), 86–97.

L.W. Beineke, Minimal decompositions of complete graphs into subgraphs with embeddability properties, Canad. J. Math. 21 (1969), 992–1000.

L.W. Beineke and F.Harary, On the thickness of the complete graph, Bull. Amer. Math. Soc. 70 (1964), 618–620.

L.W. Beineke and F.Harary, The thickness of the complete graph, Canad. J. Math. 17 (1965), 850–859.

L.W. Beineke, F.Harary and J.W. Moon, On the thickness of the complete bipartite graph, Proc. Cambridge Philos. Soc. 60 (1964), 1–5.

J.A. Bondy and U.S.R. Murty, Graph theory, Graduate Texts in Mathematics, vol. 244, Springer, New York, 2008.

N.K. Bose and K.A. Prablu, Thickness of graphs with degree constrained vertices, IEEE Trans. on Circuits and Systems 24 (1977), 184–190.

G. Brinkmann, K. Coolsaet, J. Goedgebeur and H. Me ́lot, House of Graphs: a database of interesting graphs, Discrete Appl. Math. 161 (1-2) (2013), 311–314, Available at http://hog.grinvin.org. Accessed: 2018-02-14.

H. Castan ̃eda-Lo ́pez, P.C. Palomino, A.B. Ramos-Tort, C. Rubio-Montiel and C. Silva-Ru ́ız, The 6-girth-thickness of the complete graph, arXiv:1709.07466, in review.

R.K. Guy and R.J. Nowakowski, The outer thickness & outer coarseness of graphs. I. The complete graph & the n-cube, Topics in combinatorics and graph theory, Physica-Verlag HD, 1990, 297–310.

S. Isao and H. Ozaki, On the planar decomposition of a complete bipartite graph, Siam J. Appl. Math. 16 (2) (1968), 408–416.

B. Jackson and G. Ringel, Variations on Ringel’s earth-moon problem, Discrete Math. 211 (1-3) (2000), 233–242.

M. Kleinert, Die Dicke des n-dimensionalen Wu ̈rfel-Graphen, J. Combin. Theory 3 (1967), 10–15.

A. Mansfield, Determining the thickness of graphs is NP-hard, Math. Proc. Cambridge Philos. Soc. 93 (1) (1983), 9–23.

P. Mutzel, T. Odenthal and M. Scharbrodt, The thickness of graphs: a survey, Graphs Combin. 14 (1) (1998), 59–73.

C. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964), 12.

C. Rubio-Montiel, The 4-girth-thickness of the complete graph, Ars Math. Contemp. 14 (2) (2018), 319–327.

W.T. Tutte, The thickness of a graph, Indag. Math. 25 (1963), 567–577.

Y. Yang, A note on the thickness of Kl,m,n, Ars Combin. 117 (2014), 349–351.

Y. Yang, Remarks on the thickness of Kn,n,n, Ars Math. Contemp. 12 (1) (2017), 135–144.


Refbacks

  • There are currently no refbacks.


ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats