The number of k-colorings of a graph on a fixed surface

We prove that, for every fixed surface S, there exists a largest positive constant c such that every 5-colorable graph with n vertices on S has at least c·2ⁿ distinct 5-colorings. This is best possible in the sense that, for each sufficiently large natural number n, there is a graph with n vertices on S that has precisely c·2ⁿ distinct 5-colorings. For the sphere the constant c is , and for each other surface, it is a finite problem to determine c. There is an analogous result for k-colorings for each natural number k>5.     

The quasi order of graphs on an ordinal

For α an ordinal, a graph with vertex set α may be represented by its characteristic function, f:[α]²→2, where f({γ,δ})=1 if and only if the pair {γ,δ} is joined in the graph. We call these functions α-colorings.We introduce a quasi order on the α-colorings (graphs) by setting f≤g if and only if there is an order-preserving mapping t:α→α such that f({γ,δ})=g({t(γ),t(δ)}) for all {γ,δ}∈[α]². An α-coloring f is an atom if g≤f implies f≤g.We show that for α=ω^ω below every coloring there is an atom and there are continuum many atoms. For α<ω^ω below every coloring there is an atom and there are finitely many atoms.     

On covering expander graphs by hamilton cycles

The problem of packing Hamilton cycles in random and pseudorandom graphs has been studied extensively. In this paper, we look at the dual question of covering all edges of a graph by Hamilton cycles and prove that if a graph with maximum degree Δ satisfies some basic expansion properties and contains a family of edge disjoint Hamilton cycles, then there also exists a covering of its edges by Hamilton cycles. This implies that for every α > 0 and every there exists a covering of all edges of G(n,p) by Hamilton cycles asymptotically almost surely, which is nearly optimal.Copyright © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 44, 183‐200, 2014     

A separator theorem for graphs of bounded genus

Many divide-and-conquer algorithms on graphs are based on finding a small set of vertices or edges whose removal divides the graph roughly in half. Most graphs do not have the necessary small separators, but some useful classes do. One such class is planar graphs: If an n-vertex graph can be drawn on the plane, then it can be bisected by removal of O(sqrt(n)) vertices (R. J. Lipton and R. E. Tarjan, SIAM J. Appl. Math.36 (1979), 177–189). The main result of the paper is that if a graph can be drawn on a surface of genus g, then it can be bisected by removal of O(sqrt(gn)) vertices. This bound is best possible to within a constant factor. An algorithm is given for finding the separator that takes time linear in the number of edges in the graph, given an embedding of the graph in its genus surface. Some extensions and applications of these results are discussed.     

On the hyperbolicity constant in graphs

If X is a geodesic metric space and x₁,x₂,x₃∈X, a geodesic triangleT={x₁,x₂,x₃} is the union of the three geodesics [x₁x₂], [x₂x₃] and [x₃x₁] in X. The space X is δ-hyperbolic (in the Gromov sense) if, for every geodesic triangle T in X, every side of T is contained in a δ-neighborhood of the union of the other two sides. We denote by δ(X) the sharpest hyperbolicity constant of X, i.e. . In this paper, we obtain several tight bounds for the hyperbolicity constant of a graph and precise values of this constant for some important families of graphs. In particular, we investigate the relationship between the hyperbolicity constant of a graph and its number of edges, diameter and cycles. As a consequence of our results, we show that if G is any graph with m edges with lengths , then , and if and only if G is isomorphic to C_m. Moreover, we prove the inequality for every graph, and we use this inequality in order to compute the precise value δ(G) for some common graphs.     

On conditional edge-connectivity of graphs

1. IntroductionIn this paper, a graph G ~ (V,E) always means a simple graph (without loops andmultiple edges) with the vertex-set V and the edge-set E. We follow [1] for graph-theoreticalterllilnology and notation not defined here.It is well known that when the underlying topology of a computer interconnectionnetwork is modeled by a graph G, the edge-connectivity A(G) of G is an important measurefor fault-tolerance of the network. However, it has many deficiencies (see [2]). MotiVatedby t…     

The orientable genus of some joins of complete graphs with large edgeless graphs

In an earlier paper the authors showed that with one exception the nonorientable genus of the graph with m≥n−1, the join of a complete graph with a large edgeless graph, is the same as the nonorientable genus of the spanning subgraph . The orientable genus problem for with m≥n−1 seems to be more difficult, but in this paper we find the orientable genus of some of these graphs. In particular, we determine the genus of when n is even and m≥n, the genus of when n=2^p+2 for p≥3 and m≥n−1, and the genus of when n=2^p+1 for p≥3 and m≥n+1. In all of these cases the genus is the same as the genus of K_m,n, namely ⌈(m−2)(n−2)/4⌉.     

Exponentially many maximum genus embeddings and genus embeddings for complete graphs

There are many results on the maximum genus, among which most are written for the existence of values of such embeddings, and few attention has been paid to the estimation of such embeddings and their applications. In this paper we study the number of maximum genus embeddings for a graph and find an exponential lower bound for such numbers. Our results show that in general case, a simple connected graph has exponentially many distinct maximum genus embeddings. In particular, a connected cubic graph G of order n always has at least distinct maximum genus embeddings, where α and m denote, respectively, the number of inner vertices and odd components of an optimal tree T. What surprise us most is that such two extremal embeddings (i.e., the maximum genus embeddings and the genus embeddings) are sometimes closely related with each other. In fact, as applications, we show that for a sufficient large natural number n, there are at least many genus embeddings for complete graph K _n with n ≡ 4, 7, 10 (mod12), where C is a constance depending on the value of n of residue 12. These results improve the bounds obtained by Korzhik and Voss and the methods used here are much simpler and straight. This work was supported by the National Natural Science Foundation of China (Grant No. 10671073), Science and Technology commission of Shanghai Municipality (Grant No. 07XD14011) and Shanghai Leading Academic Discipline Project (Grant No. B407)     

On hereditary clique-Helly self-clique graphs

A graph is clique-Helly if any family of mutually intersecting (maximal) cliques has non-empty intersection, and it is hereditary clique-Helly (HCH) if its induced subgraphs are clique-Helly. The clique graph of a graph G is the intersection graph of its cliques, and G is self-clique if it is connected and isomorphic to its clique graph. We show that every HCH graph is an induced subgraph of a self-clique HCH graph, and give a characterization of self-clique HCH graphs in terms of their constructibility starting from certain digraphs with some forbidden subdigraphs. We also specialize this results to involutive HCH graphs, i.e. self-clique HCH graphs whose vertex-clique bipartite graph admits a part-switching involution.     

On total 9‐coloring planar graphs of maximum degree seven

Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999     

On bounded treewidth duality of graphs

For a graph H, the H-coloring problem is to decide whether or not an instance graph G is homomorphic to H. The H-coloring problem is said to have bounded treewidth duality if there is an integer k such that for any graph G which is not homomorphic to H, there is a graph F of treewidth k which is homomorphic to G but not homomorphic to H. It is known that if the H-coloring problem has bounded treewidth duality then it is polynomial time decidable. We shall prove in this paper that for any integers m, k, there is an integer n₀ such that if G is a graph of girth ≥ n₀ then any graph F of treewidth k homomorphic to G is also homomorphic to C_2m+1. It follows from this result that for non-bipartite graphs H, the H-coloring problems do not have bounded treewidth duality. We also present some classes of directed graphs H for which the H-coloring problems do not have bounded treewidth duality. In particular, there are oriented cycles H for which the H-coloring problems do not have bounded treewidth duality. This answers a question of Hell and Zhu (Siam J. Discrete Math., 8 (1995), 208–222). © 1996 John Wiley & Sons, Inc.     

Randomized k-server algorithms for growth-rate bounded graphs

The k-server problem is a fundamental online problem where k mobile servers should be scheduled to answer a sequence of requests for points in a metric space as to minimize the total movement cost. While the deterministic competitive ratio is at least k, randomized k-server algorithms have the potential of reaching o(k)-competitive ratios. Prior to this work only few specific cases of this problem were solved. For arbitrary metric spaces, this goal may be approached by using probabilistic metric approximation techniques. This paper gives the first results in this direction, obtaining o(k)-competitive ratio for a natural class of metric spaces, including d-dimensional grids, and wide range of k.     

On the convergence of metric and geometric properties of polyhedral surfaces

We provide conditions for convergence of polyhedral surfaces and their discrete geometric properties to smooth surfaces embedded in Euclidean 3-space. Under the assumption of convergence of surfaces in Hausdorff distance, we show that convergence of the following properties are equivalent: surface normals, surface area, metric tensors, and Laplace–Beltrami operators. Additionally, we derive convergence of minimizing geodesics, mean curvature vectors, and solutions to the Dirichlet problem. This work was supported by the DFG Research Center Matheon “Mathematics for key technologies” in Berlin.     

Polychromatic colorings of bounded degree plane graphs

A polychromatic k‐coloring of a plane graph G is an assignment of k colors to the vertices of G such that every face of G has all k colors on its boundary. For a given plane graph G, one seeks the maximum number k such that G admits a polychromatic k ‐coloring. In this paper, it is proven that every connected plane graph of order at least three, and maximum degree three, other than K₄ or a subdivision of K₄ on five vertices, admits a 3‐coloring in the regular sense (i.e., no monochromatic edges) that is also a polychromatic 3‐coloring. Our proof is constructive and implies a polynomial‐time algorithm. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 269‐283, 2009     

Partial duality and Bollobás and Riordan’s ribbon graph polynomial

Recently S. Chmutov introduced a generalization of the dual of a ribbon graph (or equivalently an embedded graph) and proved a relation between Bollobás and Riordan’s ribbon graph polynomial of a ribbon graph and of its generalized duals. Here I show that the duality relation satisfied by the ribbon graph polynomial can be understood in terms of knot theory and I give a simple proof of the relation which used the homfly polynomial of a knot.     

Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface

A polyhedral embedding in a surface is one in which any two faces have boundaries that are either disjoint or simply connected. In a cubic (3-regular) graph this is equivalent to the dual being a simple graph. In 1968, Grünbaum conjectured that every cubic graph with a polyhedral embedding in an orientable surface is 3-edge-colorable. For the sphere, this is equivalent to the Four-Color Theorem, but we have disproved the conjecture in the general form. In this paper we extend this result and show that if we restrict our attention to a class of cubic graphs with a polyhedral embedding in an orientable surface, then the computational complexity of the 3-edge-coloring problem and its approximation does not improve.