×

The 6-girth-thickness of the complete graph. (English) Zbl 1468.05048

Summary: The \(g\)-girth-thickness \(\theta (g,G)\) of a graph \(G\) is the minimum number of planar subgraphs of girth at least \(g\) whose union is \(G\). In this paper, we determine the 6-girth-thickness \(\theta (6, K_n )\) of the complete graph \(K_n \) in almost all cases. And also, we calculate by computer the missing value of \(\theta (4,K_n )\).

MSC:

05C10 Planar graphs; geometric and topological aspects of graph theory

Software:

House of Graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aggarwal, A.; Klawe, M.; Shor, P., Multilayer grid embeddings for VLSI, Algorithmica, 6, 1-6, 129-151 (1991) · Zbl 0703.68044
[2] Alekseev, V. B.; Gončakov, V. S., The thickness of an arbitrary complete graph, Mat. Sb. (N.S.), 101, 143, 212-230 (1976) · Zbl 0344.05140
[3] Araujo-Pardo, G.; Contreras-Mendoza, F. E.; Murillo-García, S. J.; Ramos-Tort, A. B.; Rubio-Montiel, C., Complete colorings of planar graphs, Discrete Appl. Math., 255, 86-97 (2019) · Zbl 1405.05051
[4] Beineke, L. W., Minimal decompositions of complete graphs into subgraphs with embeddability properties, Can. J. Math., 21, 992-1000 (1969) · Zbl 0181.51704
[5] Beineke, L. W.; Harary, F., On the thickness of the complete graph, Bull. Am. Math. Soc., 70, 4, 618-620 (1964) · Zbl 0123.39903
[6] Beineke, L. W.; Harary, F., The thickness of the complete graph, Can. J. Math., 17, 850-859 (1965) · Zbl 0135.42104
[7] Beineke, L. W.; Harary, F.; Moon, J. W., On the thickness of the complete bipartite graph, Proc. Cambridge Philos. Soc., 60, 1-5 (1964) · Zbl 0121.18402
[8] Bondy, J. A.; Murty, U. S. R., Graph Theory, Graduate Texts in Mathematics, 244 (2008), New York: Springer, New York · Zbl 1134.05001
[9] Brinkmann, G.; Coolsaet, K.; Goedgebeur, J.; Mélot, H., House of Graphs: a database of interesting graphs, Discrete Appl. Math., 161, 1-2, 311-314 (2013) · Zbl 1292.05254
[10] Chartrand, G.; Zhang, P., Chromatic graph theory (2009), Boca Raton, FL: CRC Press · Zbl 1169.05001
[11] Chen, Y.; Yang, Y., The thickness of the complete multipartite graphs and the join of graphs, J. Comb. Optim., 34, 1, 194-202 (2017) · Zbl 1407.90271
[12] Guy, R. K.; Nowakowski, R. J., Topics in Combinatorics and Graph Theory (Oberwolfach, 1990), The outerthickness & outercoarseness of graphs. I. The complete graph & the n-cube, 297-310 (1990), Heidelberg: Physica, Heidelberg · Zbl 0742.05069
[13] Jackson, B.; Ringel, G., Variations on Ringel’s earth-moon problem, Discrete Math, 211, 1-3, 233-242 (2000) · Zbl 0945.05019
[14] Kleinert, M., Die Dicke des n-dimensionalen Würfel-Graphen, J. Comb. Theory, 3, 1, 10-15 (1967) · Zbl 0152.41101
[15] Mansfield, A., Determining the thickness of graphs is NP-hard, Math. Proc. Cambridge Philos. Soc, 93, 1, 9-23 (1983) · Zbl 0503.68048
[16] Mutzel, P.; Odenthal, T.; Scharbrodt, M., The thickness of graphs: a survey, Graphs Comb., 14, 1, 59-73 (1998) · Zbl 0896.05020
[17] Rubio-Montiel, C., The 4-girth-thickness of the complete graph, Ars Math. Contemp., 14, 2, 319-327 (2017) · Zbl 1393.05092
[18] Rubio-Montiel, C., The 4-girth-thickness of the multipartite complete graph, Electron. J. Graph Theory Appl., 7, 1, 83-188 (2019) · Zbl 1467.05052
[19] Tutte, W. T., The thickness of a graph, Indag. Math., 66, 567-577 (1963) · Zbl 0123.17002
[20] Vasak, J. M., The thickness of the complete graphs (1976)
[21] Yang, Y., A note on the thickness of, Ars Comb., 117, 349-351 (2014) · Zbl 1340.05051
[22] Yang, Y., Remarks on the thickness of, Ars Math. Contemp., 12, 1, 135-144 (2016) · Zbl 1370.05051
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.