scientific article; zbMATH DE number 15359

MaRDI QIDQ3972003zbMATH OpenFDO

Authors Richard K. Guy, R. J. Nowakowski

Publication date 25 June 1992

zbMATH Keywords

\(n\)-cubecomplete graphoutercoarsenessouterthickness

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

The outerthickness of a graph \(G\) is the minimum number of sets in a partition of \(E(G)\) such that each set induces an outerplanar graph. The outercoarseness of a graph \(G\) is the maximum number of sets in a partition of \(E(G)\) such that each set induces a non-outerplanar graph. Four results (some of which were announced without proof [\textit{R. K. Guy}, ``Outerthickness and outercoarseness of graphs, Combinatorics, Proc. British combin. Conf., Aberystwyth 1973, 57--60 (1974; Zbl 0293.05108)]) are proved. Theorem 1. The outerthickness of \(K_n\) is \(\lceil(n+1)/4\rceil\), except that the outerthickness of \(K_7\) is 3. Theorem 2. The outerthickness of the \(n\)-cube is \(\lceil(n+1)/3\rceil\). Theorem 3. The outercoarseness of \(K_n\) is \(\lfloor n(n-1)/12\rfloor\). Theorem 4. The outercoarseness of the \(n\)-cube is between \((0.96n- 1.15)2^{n-4}\) and \(n2^{n-4}\) except that the lower bound may not hold for \(n=2, 5, 6\), and \(9\). Theorem 3 was first proved by \textit{L. W. Beineke} [The many facets of graph theory, Proc. Conf. Western Michigan Univ., Kalamazoo/Mi. 1968, 45--53 (1969; Zbl 0186.27601)]. [For the entire collection see Zbl 0698.00017.]

Recommendations

• scientific article; zbMATH DE number 4208089
• Remarks on the thickness and outerthickness of a graph
• The outercoarseness of the n-cube
• Thickness and outerthickness for embedded graphs
• The thickness of \(K_{1,n,n}\) and \(K_{2,n,n}\)

Cited in

(17)

• Thickness-two graphs. II: More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs
• Complete colorings of planar graphs
• Thickness and outerthickness for embedded graphs
• Thickness of the subgroup intersection graph of a finite group
• scientific article; zbMATH DE number 4208089 (Why is no real title available?)
• Outerplanar coarseness of planar graphs
• scientific article; zbMATH DE number 4057557 (Why is no real title available?)
• scientific article; zbMATH DE number 722456 (Why is no real title available?)
• The 4-girth-thickness of the complete graph
• The outercoarseness of the n-cube
• The 6-girth-thickness of the complete graph
• The 4-girth-thickness of the complete multipartite graph
• The Local Queue Number of Graphs with Bounded Treewidth
• On graph thickness, geometric thickness, and separator theorems
• On the uncrossed number of graphs
• Thickness of line graph of intersection graph of ideals of rings
• Remarks on the thickness and outerthickness of a graph

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3972003)