Mathematical Research of Dr. John Maharry

My research is in graph theory. Specifically in structural graph theory, graph minors, topological graph theory and graph algorithms.

A graph is a network of nodes or vertices and edges or connections between them. Graphs can represent cities with roads connecting them, or internet sites connected by links, circuit diagrams, almost any set of objects with various connections among them.

Much of my research centers on trying to determine structures (planarity, surface embeddings, connectivity, bounded tree-width) that guarantees the existance of certain graphs. Some of this is related to the idea of Ramsey Theory, namely the following concept: In any "random" structure, if it is large enough, there must be some smaller "nice" structure inside.

A nice example of that was in "A Beautiful Mind" when John Nash was able to find an "umbrella" structure given enough randomly placed stars. A simple graph theory problem is that, for any value of k, any large enough connected graph must contain one of two structures, a vertex with at least k neighbors, or a path of at least k vertices long. In my research, for example, we show that, for any k, one can find a certain graph structure, a K3,k-minor, in any large enough 7-connected graph.

A selection of recent papers:

1. de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, R. B.; Salazar, G. Improved bounds for the crossing numbers of $K\sb {m,n}$ and $K\sb n$. SIAM J. Discrete Math. 20 (2006), no. 1, 189--202 (electronic).
2. Böhme, Thomas; Maharry, John; Mohar, Bojan $K\sb {a,k}$ minors in graphs of bounded tree-width. J. Combin. Theory Ser. B 86 (2002), no. 1, 133--147.
3. Maharry, John A characterization of graphs with no cube minor. J. Combin. Theory Ser. B 80 (2000), no. 2, 179--201.
4. Sanders, Daniel P.; Maharry, John On simultaneous colorings of embedded graphs. Discrete Math. 224 (2000), no. 1-3, 207--214.
5. Maharry, John An excluded minor theorem for the octahedron. J. Graph Theory 31 (1999), no. 2, 95--100.
6. Maharry, John A splitter for graphs with no Petersen family minor. J. Combin. Theory Ser. B 72 (1998), no. 1, 136--139.
7. Boehme, Thomas; Kawarabayashi, Ken-Ichi: Maharry,John; Mohar, Bojan, Linear Connectivity Forces Large Complete Bipartite Minors, submitted to JCTB
8. Maharry, John, An excluded minor theorem for the Octahedron plus an edge, to appear in the Journal of Graph Theory.
9. Maharry, John, Three Excluded Minor Structure Theorems, submitted to Journal of Graph Theory.
10. Boehme, Thomas; Kawarabayashi, Ken-Ichi; Maharry,John; Mohar, Bojan, K3,k-minors in large graphs , In preparation.
11. Maharry, John; Slilaty, Dan, Projective Planar Graphs with No K3,4-minor, in preparation.