TOPICS
Search

Graph Coarseness

The coarseness xi(G) of a graph G is the maximum number of edge-disjoint nonplanar subgraphs contained in a given graph G. The coarseness of a planar graph G is therefore xi(G)=0.

The coarseness of a graph is the sum of the coarsenesses of its blocks (Beineke and Chartrand 1968).

The coarseness of the complete graph K_n is known for most values of n except n=13, n divisible by 3 and greater than or equal to 18, and n of the form 9k+7. For all of these, the values are known to within 1 (Guy and Beineke 1968; Harary 1994, pp. 121-122).

The coarseness of the complete bipartite graph K_(m,n) is known for values of m,n satisfying certain conditions (Beineke and Guy 1969; Harary 1994, pp. 121-122).

See also

Graph Thickness, Nonplanar Graph

Explore with Wolfram|Alpha

References

Beineke, L. W. and Chartrand, G. "The Coarseness of a Graph." Compos. Math. 19, 290-298, 1968.Beineke, L. W. and Guy, R. K. "The Coarseness of the Complete Bipartite Graph." Canad. J. Math. 21, 1086-1096, 1969.Guy, R. and Beineke, L. "'THe Coarseness of the Complete Graph." Canad. J. Math. 20, 888-894, 1968.Harary, F. "Covering and Packing in Graphs, I." Ann. New York Acad. Sci. 175, 198-205, 1970.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, pp. 121-122, 1994.Harary, F. and Palmer, E. M. Graphical Enumeration. New York: Academic Press, p. 225, 1973.Harary, F. and Palmer, E. M. "A Survey of Graph Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam: North-Holland, pp. 259-275, 1973.Kainen, P. C. "Thickness and Coarseness of Graphs." Abh. Math. Semin. Univ. Hamburg 39, 88-95, 1973.

Referenced on Wolfram|Alpha

Graph Coarseness

Cite this as:

Weisstein, Eric W. "Graph Coarseness." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GraphCoarseness.html

Subject classifications