TOPICS
Search

Plummer-Toft Graph


The name "Plummer-Toft graphs" is used in this work for the first of two infinite families noted by Plummer and Toft (1987) that attain the conjectured bound described below.

Let q be the maximum number of vertices incident with a graph face of a graph (the maximum face degree) and chi_c its cyclic chromatic number. It is conjectured that chi_c<=q+2 for polyhedral graphs (Plummer and Toft 1987).

PlummerToftGraphs

The first few Plummer-Toft graphs are illustrated above in three different types of embeddings.

The 2-Plummer-Toft graph is an outer-cylindrical forbidden minor gamma_1 (No. 12; Archdeacon et al. 2001).


See also

Cyclic Chromatic Number, Outer-Cylindrical Graph

Explore with Wolfram|Alpha

References

Archdeacon, D.; Bonnington, C. P.; Dean, N.; Hartsfield, N.; and Scott, K. "Obstruction Sets for Outer-Cylindrical Graphs." J. Graph Th. 38, 42-64, 2001. https://doi.org/10.1002/jgt.1023.House of Graphs. Plummer-Toft Graphs. Self Dual Graph 1.Plummer, M. D. and Toft, B. "Cyclic Coloration of 3-Polytopes." J. Graph Th. 11, 507-515, 1987.

Referenced on Wolfram|Alpha

Plummer-Toft Graph

Cite this as:

Weisstein, Eric W. "Plummer-Toft Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Plummer-ToftGraph.html

Subject classifications