The 4-girth-thickness of the complete graph

Christian Rubio-Montiel

Abstract


In this paper, we define the 4-girth-thickness θ(4, G) of a graph G as the minimum number of planar subgraphs of girth at least 4 whose union is G. We prove that the 4-girth-thickness of an arbitrary complete graph Kn, θ(4, Kn), is ⌈(n+2)/4⌉ for n ≠ 6, 10 and θ(4, K6)=3.


Keywords


Thickness, planar decomposition, girth, complete graph

Full Text:

PDF ABSTRACTS (EN/SI)


ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications