Computational graph theory
- 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.
- Links to award summaries for each source of funding
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
- Links to project's websites