Computational graph theory

From CCM
Jump to: navigation, search
A graph is said to have thickness t if its edges can be partitioned in to t, and no fewer, planar graphs. The highest chromatic number over all thickness-t graphs is known only in the case t=1, which is due to the famous Four Color Theorem. The same kinds of questions can be asked for graphs, both orientable and non-orientable, on other surfaces. In this project we use computational methods to search for high chromatic thickness-t graphs on a variety of orientable surfaces.



To produce new high chromatic thickness-t graphs, t>2, for graphs on the sphere and other orientable surfaces.

Major results


Project lead

Ellen Gethner


Roqyah Alalqam



Links to award summaries for each source of funding

Recent publications

Journal articles

Ferrara, Michael; Flesch, Breeann; Gethner, Ellen List-distinguishing colorings of graphs. Electron. J. Combin. 18 (2011), no. 1, Research Paper 161, 17 pp, 05C15 (05C25)

Gethner, Ellen; Laison, Joshua D. More directions in visibility graphs. Australas. J. Combin. 50 (2011), 55–65, 05C62

Albertson, Michael O.; Boutin, Debra L.; Gethner, Ellen More results on r-inflated graphs: arboricity, thickness, chromatic number and fractional chromatic number. Ars Math. Contemp. 4 (2011), no. 1, 5–24, 05C15 (05C10 05C42)

Albertson, Michael O.; Boutin, Debra L.; Gethner, Ellen The thickness and chromatic number of r-inflated graphs. Discrete Math. 310 (2010), no. 20, 2725–2734. (Reviewer: Arthur M. Hobbs), 05C76 (05C10 05C15 05C69)

Ferrara, Michael; Lee, Christine; Wallis, Phil; Gethner, Ellen deBruijn-like sequences and the irregular chromatic number of paths and cycles. Discrete Math. 309 (2009), no. 20, 6074–6080, 05A05 (05C15 05C38)

Gethner, Ellen; Kallichanda, Bopanna; Mentis, Alexander S.; Braudrick, Sarah; Chawla, Sumeet; Clune, Andrew; Drummond, Rachel; Evans, Panagiota; Roche, William; Takano, Nao How false is Kempe's proof of the four color theorem? II. Involve 2 (2009), no. 3, 249–266, 05C85 (05C15)

Gethner, Ellen; Sulanke, Thom Thickness-two graphs. II. More new nine-critical graphs, independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs. Graphs Combin. 25 (2009), no. 2, 197–217. 05C10 (05C15)

Boutin, Debra L.; Gethner, Ellen; Sulanke, Thom Thickness-two graphs. I. New nine-critical graphs, permuted layer graphs, and Catlin's graphs. J. Graph Theory 57 (2008), no. 3, 198–214.


Ellen Gethner, David Kirkpatrick, and Nicholas Pippenger. M.C Escher Wrap Artist: Aesthetic Coloring of Ribbon Patterns, forthcoming

External links

Links to project's websites


See also

Personal tools