3‐Coloring graphs embedded in surfaces

In this article, we show that there exists an integer k(Σ) ≥ 5 such that, if G is a graph embedded in a surface Σ without i‐circuits, 4 ≤ i ≤ k(Σ), then G is 3‐colorable. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 140–143, 2000     

2‐ and 3‐factors of graphs on surfaces

It has been conjectured that any 5‐connected graph embedded in a surface Σ with sufficiently large face‐width is hamiltonian. This conjecture was verified by Yu for the triangulation case, but it is still open in general. The conjecture is not true for 4‐connected graphs. In this article, we shall study the existence of 2‐ and 3‐factors in a graph embedded in a surface Σ. A hamiltonian cycle is a special case of a 2‐factor. Thus, it is quite natural to consider the existence of these factors. We give an evidence to the conjecture in a sense of the existence of a 2‐factor. In fact, we only need the 4‐connectivity with minimum degree at least 5. In addition, our face‐width condition is not huge. Specifically, we prove the following two results. Let G be a graph embedded in a surface Σ of Euler genus g.

• (1) If G is 4‐connected and minimum degree of G is at least 5, and furthermore, face‐width of G is at least 4g?12, then G has a 2‐factor.
• (2) If G is 5‐connected and face‐width of G is at least max{44g?117, 5}, then G has a 3‐factor.

The connectivity condition for both results are best possible. In addition, the face‐width conditions are necessary too. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 67:306‐315, 2011     

Orientation embedding of signed graphs

A signed graph Σ consists of a graph and a sign labeling of its edges. A polygon in Σ is “balanced” if its sign product is positiive. A signed graph is “orientatio embedded” in a surface if it is topologically embedded and a polygon is balanced precisely when traveling once around it preserves orientation. We explore the extension to orientation embedding of the ordinary theory of graph embedding. Let d(Σ) be the demigenus (= 2 - x(S)) of the unique smallest surface S in which Σ has an orientation embedding. Our main results are an easy one, that if Σ has connected components Σ₁, Σ[2], ?, then d(Σ) = d(Σ₁) + ?, and a hard one, that if Σ has a cut vertex v that splits Σ into Σ₁, Σ₂, ?, then d(Σ) = d(Σ₁) + d(Σ₂) + ? -δ, where δ depends on the number of Σ_i in which v is “loopable”, that is, in which d(Σ_i) = d(Σ_{i with a negative loop added to v}). This is as with ordinary orientable grpah embedidng except for the existence of the term δ in the cut-vertex formula. Since loopability is crucial, we give some partial criteria for it. (A complete characterization seems difficult.) We conclude with an application to forbidden subgraphs and minors for orientation embeddability in a given surface. © 1929 John Wiley & Sons, Inc.     

Weinberg bounds over nonspherical graphs

Let Aut(G) and E(G) denote the automorphism group and the edge set of a graph G, respectively. Weinberg's Theorem states that 4 is a constant sharp upper bound on the ratio |Aut(G)|/|E(G)| over planar (or spherical) 3‐connected graphs G. We have obtained various analogues of this theorem for nonspherical graphs, introducing two Weinberg‐type bounds for an arbitrary closed surface Σ, namely: where supremum is taken over the polyhedral graphs G with respect to Σ for W_P(Σ) and over the graphs G triangulating Σ for W_T(Σ). We have proved that Weinberg bounds are finite for any surface; in particular: W_P = W_T = 48 for the projective plane, and W_T = 240 for the torus. We have also proved that the original Weinberg bound of 4 holds over the graphs G triangulating the projective plane with at least 8 vertices and, in general, for the graphs of sufficiently large order triangulating a fixed closed surface Σ. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 220–236, 2000     

Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree

We show that if G has a minor M with maximum degree at most 4, then the crossing number of G in a surface Σ is at least one fourth the crossing number of M in Σ. We use this result to show that every graph embedded on the torus with representativity r ≥ 6 has Klein bottle crossing number at least ⌊2r/3⌋²/64. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 168–173, 2001     

Total chromatic number of graphs with small genus

Given a graph G, a total k-coloring of G is a simultaneous coloring of the vertices and edges of G with k colors. Denote χ_ve (G) the total chromatic number of G, and c(Σ) the Euler characteristic of a surfase Σ. In this paper, we prove that for any simple graph G which can be embedded in a surface Σ with Euler characteristic c(Σ), χ_ve (G) = Δ (G) + 1 if c(Σ) > 0 and Δ (G) ≥ 13, or, if c(Σ) = 0 and Δ (G) ≥ 14. This result generalizes results in [3], [4], [5] by Borodin.     

The 3‐connectivity of a graph and the multiplicity of zero “2” of its chromatic polynomial

Let G be a graph of order n, maximum degree Δ, and minimum degree δ. Let P(G, λ) be the chromatic polynomial of G. It is known that the multiplicity of zero “0” of P(G, λ) is one if G is connected, and the multiplicity of zero “1” of P(G, λ) is one if G is 2‐connected. Is the multiplicity of zero “2” of P(G, λ) at most one if G is 3‐connected? In this article, we first construct an infinite family of 3‐connected graphs G such that the multiplicity of zero “2” of P(G, λ) is more than one, and then characterize 3‐connected graphs G with Δ + δ?n such that the multiplicity of zero “2” of P(G, λ) is at most one. In particular, we show that for a 3‐connected graph G, if Δ + δ?n and (Δ, δ₃)≠(n?3, 3), where δ₃ is the third minimum degree of G, then the multiplicity of zero “2” of P(G, λ) is at most one. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Coloring edges of embedded graphs

In this paper, we prove that any graph G with maximum degree , which is embeddable in a surface Σ of characteristic χ(Σ) ≤ 1 and satisfies , is class one. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 197–205, 2000     

Finding for a Surface Σ of Characteristic −4

For each surface Σ, we define max G is a class two graph of maximum degree that can be embedded in . Hence, Vizing's Planar Graph Conjecture can be restated as if Σ is a sphere. In this article, by applying some newly obtained adjacency lemmas, we show that if Σ is a surface of characteristic . Until now, all known satisfy . This is the first case where .     

Vertex-transitive graphs: Symmetric graphs of prime valency

Let G be a group acting symmetrically on a graph Σ, let G₁ be a subgroup of G minimal among those that act symmetrically on Σ, and let G₂ be a subgroup of G₁ maximal among those normal subgroups of G₁ which contain no member except 1 which fixes a vertex of Σ. The most precise result of this paper is that if Σ has prime valency p, then either Σ is a bipartite graph or G₂ acts regularly on Σ or G₁ | G₂ is a simple group which acts symmetrically on a graph of valency p which can be constructed from Σ and does not have more vertices than Σ. The results on vertex-transitive groups necessary to establish results like this are also included.     

Rigidity of Area-Minimizing Hyperbolic Surfaces in Three-Manifolds

We prove that if M is a three-manifold with scalar curvature greater than or equal to ?2 and Σ?M is a two-sided compact embedded Riemann surface of genus greater than 1 which is locally area-minimizing, then the area of Σ is greater than or equal to 4π(g(Σ)?1), where g(Σ) denotes the genus of Σ. In the equality case, we prove that the induced metric on Σ has constant Gauss curvature equal to ?1 and locally M splits along Σ. We also obtain a rigidity result for cylinders (I×Σ,dt ²+g _Σ), where I=[a,b]?? and g _Σ is a Riemannian metric on Σ with constant Gauss curvature equal to ?1.     

On the edge reconstruction of graphs embedded on surfaces

In this paper, we proved that ifG is a 3-connected graph of minimum valency δ = 6χ + 5 with α a non-negative integer and if there exists an embedding ψ ofG on a surface Σ of characteristic ?(Σ) = — α|V(G)∣+ β with the representativity of the embedding ψ ≥ 3, where ψ ε 0,1, thenG is edge reconstructible.     

On packing 3‐vertex paths in a graph

Let G be a connected graph and let eb(G) and λ(G) denote the number of end‐blocks and the maximum number of disjoint 3‐vertex paths Λ in G. We prove the following theorems on claw‐free graphs: (t1) if G is claw‐free and eb(G) ≤ 2 (and in particular, G is 2‐connected) then λ(G) = ⌊| V(G)|/3⌋; (t2) if G is claw‐free and eb(G) ≥ 2 then λ(G) ≥ ⌊(| V(G) | − eb(G) + 2)/3 ⌋; and (t3) if G is claw‐free and Δ^*‐free then λ(G) = ⌊| V(G) |/3⌋ (here Δ^* is a graph obtained from a triangle Δ by attaching to each vertex a new dangling edge). We also give the following sufficient condition for a graph to have a Λ‐factor: Let n and p be integers, 1 ≤ p ≤ n − 2, G a 2‐connected graph, and |V(G)| = 3n. Suppose that G − S has a Λ‐factor for every S ⊆ V(G) such that |S| = 3p and both V(G) − S and S induce connected subgraphs in G. Then G has a Λ‐factor. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 175–197, 2001     

Maximum Δ‐edge‐colorable subgraphs of class II graphs

A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory     

On G-Covering Subgroup Systems for Some Saturated Formations of Finite Groups

Let ? be a class of groups and G a finite group. We call a set Σ of subgroups of G a G-covering subgroup system for ? if G ∈ ? whenever Σ ? ?. For a non-identity subgroup H of G, we put Σ _H be some set of subgroups of G which contains at least one supplement in G of each maximal subgroup of H. Let p ≠ q be primes dividing |G|, P, and Q be non-identity a p-subgroup and a q-subgroup of G, respectively. We prove that Σ _P and Σ _P  ∪ Σ _Q are G-covering subgroup systems for many classes of finite groups.     

G-covering systems of subgroups for the class of supersoluble groups

Let ? be a class of groups. Given a group G, assign to G some set of its subgroups Σ = Σ(G). We say that Σ is a G-covering system of subgroups for ? (or, in other words, an ?-covering system of subgroups in G) if G ∈ ? wherever either Σ = ? or Σ ≠ ? and every subgroup in Σ belongs to ?. In this paper, we provide some nontrivial sets of subgroups of a finite group G which are G-covering subgroup systems for the class of supersoluble groups. These are the generalizations of some recent results, such as in [1–3].     

Acyclic edge coloring of 2‐degenerate graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a′(G). A graph is called 2‐degenerate if any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphs properly contains series–parallel graphs, outerplanar graphs, non ? regular subcubic graphs, planar graphs of girth at least 6 and circle graphs of girth at least 5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)?Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerate graphs. In fact we prove a stronger bound: we prove that if G is a 2‐degenerate graph with maximum degree Δ, then a′(G)?Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 69: 1–27, 2012     

List‐coloring the square of a subcubic graph

The square G² of a graph G is the graph with the same vertex set G and with two vertices adjacent if their distance in G is at most 2. Thomassen showed that every planar graph G with maximum degree Δ(G) = 3 satisfies χ(G²) ≤ 7. Kostochka and Woodall conjectured that for every graph, the list‐chromatic number of G² equals the chromatic number of G², that is, χ_l(G²) = χ(G²) for all G. If true, this conjecture (together with Thomassen's result) implies that every planar graph G with Δ(G) = 3 satisfies χ_l(G²) ≤ 7. We prove that every connected graph (not necessarily planar) with Δ(G) = 3 other than the Petersen graph satisfies χ_l(G²) ≤8 (and this is best possible). In addition, we show that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 7, then χ_l(G²) ≤ 7. Dvo?ák, ?krekovski, and Tancer showed that if G is a planar graph with Δ(G) = 3 and girth g(G) ≥ 10, then χ_l(G²) ≤6. We improve the girth bound to show that if G is a planar graph with Δ(G) = 3 and g(G) ≥ 9, then χ_l(G²) ≤ 6. All of our proofs can be easily translated into linear‐time coloring algorithms. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 65–87, 2008     

K4−‐factor in a graph

Let G be a graph of order 4k and let δ(G) denote the minimum degree of G. Let F be a given connected graph. Suppose that |V(G)| is a multiple of |V(F)|. A spanning subgraph of G is called an F‐factor if its components are all isomorphic to F. In this paper, we prove that if δ(G)≥5/2k, then G contains a K₄^?‐factor (K₄^? is the graph obtained from K₄ by deleting just one edge). The condition on the minimum degree is best possible in a sense. In addition, the proof can be made algorithmic. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 111–128, 2002     

Maximal K3's and Hamiltonicity of 4‐connected claw‐free graphs

Let cl(G) denote Ryjá?ek's closure of a claw‐free graph G. In this article, we prove the following result. Let G be a 4‐connected claw‐free graph. Assume that G[N_G(T)] is cyclically 3‐connected if T is a maximal K₃ in G which is also maximal in cl(G). Then G is hamiltonian. This result is a common generalization of Kaiser et al.'s theorem [J Graph Theory 48(4) (2005), 267–276] and Pfender's theorem [J Graph Theory 49(4) (2005), 262–272]. © 2011 Wiley Periodicals, Inc. J Graph Theory