Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

Search: MSC category 05C10 ( Planar graphs; geometric and topological aspects of graph theory [See also 57M15, 57M25] )

  Expand all        Collapse all Results 1 - 7 of 7

1. CMB 2017 (vol 61 pp. 55)

Chen, Yichao; Gao, Xiaojian; Huang, Yuanqiu
Enumerating unlabelled embeddings of digraphs
A $2$-cell embedding of an Eulerian digraph $D$ into a closed surface is said to be directed if the boundary of each face is a directed closed walk in $D$. In this paper, a method is developed with the purpose of enumerating unlabelled embeddings for an Eulerian digraph. As an application, we obtain explicit formulas for the number of unlabelled embeddings of directed bouquets of cycles $B_n$, directed dipoles $OD_{2n}$ and for a class of regular tournaments $T_{2n+1}$.

Keywords:Eulerian digraph, directed embedding, unlabelled embedding

2. CMB 2016 (vol 59 pp. 705)

Chen, Yichao; Yin, Xuluo
The Thickness of the Cartesian Product of Two Graphs
The thickness of a graph $G$ is the minimum number of planar subgraphs whose union is $G.$ A $t$-minimal graph is a graph of thickness $t$ which contains no proper subgraph of thickness $t.$ In this paper, upper and lower bounds are obtained for the thickness, $t(G\Box H)$, of the Cartesian product of two graphs $G$ and $H$, in terms of the thickness $t(G)$ and $t(H)$. Furthermore, the thickness of the Cartesian product of two planar graphs and of a $t$-minimal graph and a planar graph are determined. By using a new planar decomposition of the complete bipartite graph $K_{4k,4k},$ the thickness of the Cartesian product of two complete bipartite graphs $K_{n,n}$ and $K_{n,n}$ is also given, for $n\neq 4k+1$.

Keywords:planar graph, thickness, Cartesian product, $t$-minimal graph, complete bipartite graph

3. CMB 2015 (vol 59 pp. 170)

Martínez-Pedroza, Eduardo
A Note on Fine Graphs and Homological Isoperimetric Inequalities
In the framework of homological characterizations of relative hyperbolicity, Groves and Manning posed the question of whether a simply connected $2$-complex $X$ with a linear homological isoperimetric inequality, a bound on the length of attaching maps of $2$-cells and finitely many $2$-cells adjacent to any edge must have a fine $1$-skeleton. We provide a positive answer to this question. We revisit a homological characterization of relative hyperbolicity, and show that a group $G$ is hyperbolic relative to a collection of subgroups $\mathcal P$ if and only if $G$ acts cocompactly with finite edge stabilizers on an connected $2$-dimensional cell complex with a linear homological isoperimetric inequality and $\mathcal P$ is a collection of representatives of conjugacy classes of vertex stabilizers.

Keywords:isoperimetric functions, Dehn functions, hyperbolic groups
Categories:20F67, 05C10, 20J05, 57M60

4. CMB 2011 (vol 56 pp. 265)

Chen, Yichao; Mansour, Toufik; Zou, Qian
Embedding Distributions of Generalized Fan Graphs
Total embedding distributions have been known for a few classes of graphs. Chen, Gross, and Rieper computed it for necklaces, close-end ladders and cobblestone paths. Kwak and Shim computed it for bouquets of circles and dipoles. In this paper, a splitting theorem is generalized and the embedding distributions of generalized fan graphs are obtained.

Keywords:total embedding distribution, splitting theorem, generalized fan graphs

5. CMB 2008 (vol 51 pp. 535)

Csorba, Péter
On the Simple $\Z_2$-homotopy Types of Graph Complexes and Their Simple $\Z_2$-universality
We prove that the neighborhood complex $\N(G)$, the box complex $\B(G)$, the homomorphism complex $\Hom(K_2,G)$and the Lov\'{a}sz complex $\L(G)$ have the same simple $\Z_2$-homotopy type in the sense of Whitehead. We show that these graph complexes are simple $\Z_2$-universal.

Keywords:graph complexes, simple $\Z_2$-homotopy, universality
Categories:57Q10, 05C10, 55P10

6. CMB 2001 (vol 44 pp. 370)

Weston, Anthony
On Locating Isometric $\ell_{1}^{(n)}$
Motivated by a question of Per Enflo, we develop a hypercube criterion for locating linear isometric copies of $\lone$ in an arbitrary real normed space $X$. The said criterion involves finding $2^{n}$ points in $X$ that satisfy one metric equality. This contrasts nicely to the standard classical criterion wherein one seeks $n$ points that satisfy $2^{n-1}$ metric equalities.

Keywords:normed spaces, hypercubes
Categories:46B04, 05C10, 05B99

7. CMB 2000 (vol 43 pp. 108)

Sanders, Daniel P.; Zhao, Yue
On the Entire Coloring Conjecture
The Four Color Theorem says that the faces (or vertices) of a plane graph may be colored with four colors. Vizing's Theorem says that the edges of a graph with maximum degree $\Delta$ may be colored with $\Delta+1$ colors. In 1972, Kronk and Mitchem conjectured that the vertices, edges, and faces of a plane graph may be simultaneously colored with $\Delta+4$ colors. In this article, we give a simple proof that the conjecture is true if $\Delta \geq 6$.

Categories:05C15, 05C10

© Canadian Mathematical Society, 2018 :