School of Mathematics and Statistics - Research Publications
Permanent URI for this collection
Now showing 1 - 3 of 3
ItemA Note on the Cops and Robber Game on Graphs Embedded in Non-Orientable SurfacesClarke, NE ; Fiorini, S ; Joret, G ; Theis, DO (Springer Science and Business Media LLC, 2014-01-01)
ItemBoxicity of graphs on surfacesEsperet, L ; JORET, G (Springer, 2013-05)The boxicity of a graph G = (V, E) is the least integer k for which there exist k interval graphs Gi = (V, Ei), 1 ≤ i ≤ k, such that E = E1∩... ∩Ek. Scheinerman proved in 1984 that outerplanar graphs have boxicity at most two and Thomassen proved in 1986 that planar graphs have boxicity at most three. In this note we prove that the boxicity of toroidal graphs is at most 7, and that the boxicity of graphs embeddable in a surface Σ of genus g is at most 5g + 3. This result yields improved bounds on the dimension of the adjacency poset of graphs on surfaces.
ItemIrreducible triangulations are smallJoret, G ; Wood, DR (ACADEMIC PRESS INC ELSEVIER SCIENCE, 2010-09-01)