Edge colorings of graphs embeddable in a surface of low genus

In this paper, by using the Discharging Method, we show that any graph with maximum degree Δ 8 that is embeddable in a surface Σ of characteristic χ(Σ) 0 is class one and any graph with maximum degree Δ 9 that is embeddable in a surface Σ of characteristic χ(Σ) = − 1 is class one. For surfaces of characteristic 0 or −1, these results improve earlier results of Mel'nikov.     

Graphs whose acyclic graphoidal covering number is one less than its maximum degree

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. In this paper we characterize the class of graphs G for which η_a=Δ−1 where Δ is the maximum degree of a vertex in G.     

Finding the exact bound of the maximum degrees of class two graphs embeddable in a surface of characteristic

In this paper, we consider the problem of determining the maximum of the set of maximum degrees of class two graphs that can be embedded in a surface. For each surface Σ, we define Δ(Σ)=max{Δ(G)| G is a class two graph of maximum degree Δ that can be embedded in Σ}. Hence Vizing's Planar Graph Conjecture can be restated as Δ(Σ)=5 if Σ is a plane. We show that Δ(Σ)=7 if (Σ)=−1 and Δ(Σ)=8 if (Σ){−2,−3}.     

All trees are 1-embeddable and all except stars are 2-embeddable

A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))=. It is known that all trees T with n (≥2) vertices and T K_1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e};and that it is 2-embeddable if,for every pair e₁, e₂ of edges, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e₁, e₂}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K_1,n−1 are 2-embeddable. In a certain sense, this result is sharp.     

ContributionsAcyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called the path partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.     

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     

A Note on the Cops and Robber Game on Graphs Embedded in Non-Orientable Surfaces

We consider the two-player, complete information game of Cops and Robber played on undirected, finite, reflexive graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges. The cops win if, after a move, a cop and the robber are on the same vertex. The minimum number of cops needed to catch the robber on a graph is called the cop number of that graph. Let c(g) be the supremum over all cop numbers of graphs embeddable in a closed orientable surface of genus g, and likewise ${\tilde c(g)}$ for non-orientable surfaces. It is known (Andreae, 1986) that, for a fixed surface, the maximum over all cop numbers of graphs embeddable in this surface is finite. More precisely, Quilliot (1985) showed that c(g) ≤ 2g + 3, and Schröder (2001) sharpened this to ${c(g)\le \frac32g + 3}$ . In his paper, Andreae gave the bound ${\tilde c(g) \in O(g)}$ with a weak constant, and posed the question whether a stronger bound can be obtained. Nowakowski & Schröder (1997) obtained ${\tilde c(g) \le 2g+1}$ . In this short note, we show ${\tilde c(g) \leq c(g-1)}$ , for any g ≥ 1. As a corollary, using Schröder’s results, we obtain the following: the maximum cop number of graphs embeddable in the projective plane is 3, the maximum cop number of graphs embeddable in the Klein Bottle is at most 4, ${\tilde c(3) \le 5}$ , and ${\tilde c(g) \le \frac32g + 3/2}$ for all other g.     

An upper bound for the chromatic number of line graphs

It was conjectured by Reed [B. Reed, ω,α, and χ, Journal of Graph Theory 27 (1998) 177–212] that for any graph G, the graph’s chromatic number χ(G) is bounded above by , where Δ(G) and ω(G) are the maximum degree and clique number of G, respectively. In this paper we prove that this bound holds if G is the line graph of a multigraph. The proof yields a polynomial time algorithm that takes a line graph G and produces a colouring that achieves our bound.     

A combinatorial decomposition of acyclic simplicial complexes

It is proved that if Δ is a finite acyclic simplicial complex, then there is a subcomplex Δ′ Δ and a bijection η: Δ′ → Δ − Δ′ such that F η(F) and |η(F)−F|=1 for all F Δ′. This improves an earlier result of Kalai. An immediate corollary is a characterization (first due to Kalai) of the f-vector of an acyclic simplicial complex. Several generalizations, some proved and some conjectured, are discussed.     

No-hole L(2,1)-colorings

An L(2,1)-coloring of a graph G is a coloring of G's vertices with integers in {0,1,…,k} so that adjacent vertices’ colors differ by at least two and colors of distance-two vertices differ. We refer to an L(2,1)-coloring as a coloring. The span λ(G) of G is the smallest k for which G has a coloring, a span coloring is a coloring whose greatest color is λ(G), and the hole index ρ(G) of G is the minimum number of colors in {0,1,…,λ(G)} not used in a span coloring. We say that G is full-colorable if ρ(G)=0. More generally, a coloring of G is a no-hole coloring if it uses all colors between 0 and its maximum color. Both colorings and no-hole colorings were motivated by channel assignment problems. We define the no-hole span μ(G) of G as ∞ if G has no no-hole coloring; otherwise μ(G) is the minimum k for which G has a no-hole coloring using colors in {0,1,…,k}.

Let n denote the number of vertices of G, and let Δ be the maximum degree of vertices of G. Prior work shows that all non-star trees with Δ3 are full-colorable, all graphs G with n=λ(G)+1 are full-colorable, μ(G)λ(G)+ρ(G) if G is not full-colorable and nλ(G)+2, and G has a no-hole coloring if and only if nλ(G)+1. We prove two extremal results for colorings. First, for every m1 there is a G with ρ(G)=m and μ(G)=λ(G)+m. Second, for every m2 there is a connected G with λ(G)=2m, n=λ(G)+2 and ρ(G)=m.     

A special k-coloring for a connected k-chromatic graph

For each positive integer k we consider the smallest positive integer f(k) (dependent only on k) such that the following holds: Each connected graph G with chromatic number χ(G) = k can be properly vertex colored by k colors so that for each pair of vertices x_o and x_p in any color class there exist vertices x₁, x₂, …, x_p-1 of the same class with dist(x_i, x_i+1) f(k) for each i, 0 i p − 1. Thus, the graph is k-colorable with the vertices of each color class placed throughout the graph so that no subset of the class is at a distance > f(k) from the remainder of the class.

We prove that f(k) < 12k when the order of the graph is k(k − 2) + 1.     

Remarks on the bondage number of planar graphs

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. In 1998, J.E. Dunbar, T.W. Haynes, U. Teschner, and L. Volkmann posed the conjecture b(G)Δ(G)+1 for every nontrivial connected planar graph G. Two years later, L. Kang and J. Yuan proved b(G)8 for every connected planar graph G, and therefore, they confirmed the conjecture for Δ(G)7. In this paper we show that this conjecture is valid for all connected planar graphs of girth g(G)4 and maximum degree Δ(G)5 as well as for all not 3-regular graphs of girth g(G)5. Some further related results and open problems are also presented.     

Edge coloring of graphs embedded in a surface of nonnegative characteristic

Let G be a graph embeddable in a surface of nonnegative characteristic with maximum degree six. In this paper, we prove that if G contains no a vertex v which is contained in all cycles of lengths from 3 to 6, then G is of Class 1.     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

A unified approach to distance-two colouring of graphs on surfaces

In this paper we introduce the notion of Σ-colouring of a graph G: For given subsets Σ(v) of neighbours of v, for every v∈V (G), this is a proper colouring of the vertices of G such that, in addition, vertices that appear together in some Σ(v) receive different colours. This concept generalises the notion of colouring the square of graphs and of cyclic colouring of graphs embedded in a surface. We prove a general result for graphs embeddable in a fixed surface, which implies asymptotic versions of Wegner’s and Borodin’s Conjecture on the planar version of these two colourings. Using a recent approach of Havet et al., we reduce the problem to edge-colouring of multigraphs, and then use Kahn’s result that the list chromatic index is close to the fractional chromatic index. Our results are based on a strong structural lemma for graphs embeddable in a fixed surface, which also implies that the size of a clique in the square of a graph of maximum degree Δ embeddable in some fixed surface is at most $ \frac{3} {2}\Delta $ plus a constant.     

A note on minimum degree conditions for supereulerian graphs

A graph is called supereulerian if it has a spanning closed trail. Let G be a 2-edge-connected graph of order n such that each minimal edge cut SE(G) with |S|3 satisfies the property that each component of G−S has order at least (n−2)/5. We prove that either G is supereulerian or G belongs to one of two classes of exceptional graphs. Our results slightly improve earlier results of Catlin and Li. Furthermore, our main result implies the following strengthening of a theorem of Lai within the class of graphs with minimum degree δ4: If G is a 2-edge-connected graph of order n with δ(G)4 such that for every edge xyE(G) , we have max{d(x),d(y)}(n−2)/5−1, then either G is supereulerian or G belongs to one of two classes of exceptional graphs. We show that the condition δ(G)4 cannot be relaxed.     

Optimale hermite-interpolation differenzierbarer periodischer Funktionen

For the Favard class F_r in the space C_2π of continuous 2π-periodic functions we solve the following problem. Given x and knots x₀< x₁ < ··· < x_v−1., x_u− 2π we determine weights x_ki(0 k · n, 0 j < r) such that is minimal. The optimal weights are unique (except for a trivial case) and we obtain them from a system of periodic polynomial splines u_kj(0 k < n, 0 j< r): α_kj = u_kj(x). These splines induce an interpolation operator whose degree of approximation with respect to the class F_r is minimal if the knots are equidistant. Finally, we describe an efficient numerical procedure which shows how to compute the interpolation spline in the equidistant case.     

Reconstruction of infinite locally finite connected graphs

Let G be an infinite locally finite connected graph. We study the reconstructibility of G in relation to the structure of its end set . We prove that an infinite locally finite connected graph G is reconstructible if there exists a finite family (Ω_i)_0i (n2) of pairwise finitely separable subsets of such that, for all x,y,x′,y′V(G) and every isomorphism f of G−{x,y} onto G−{x′,y′} there is a permutation π of {0,…,n−1} such that for 0i<n. From this theorem we deduce, as particular consequences, that G is reconstructible if it satisfies one of the following properties: (i) G contains no end-respecting subdivision of the dyadic tree and has at least two ends of maximal order; (ii) the set of thick ends or the one of thin ends of G is finite and of cardinality greater than one. We also prove that if almost all vertices of G are cutvertices, then G is reconstructible if it contains a free end or if it has at least a vertex which is not a cutvertex.     

The W-convexity and normal structure in banach spaces

Let X be a Banach space, S(X) - x ε X : #x02016; = 1 be the unit sphere of X.The parameter, modulus of W^*-convexity, W^*(ε) = inf <(x − y)/2, f_x> : x, y S(X), x − y ≥ ε, f_x Δ_x , where 0 ≤ ε ≤ 2 and Δ_x S(X^*) be the set of norm 1 supporting functionals of S(X) at x, is investigated_ The relationship among uniform nonsquareness, uniform normal structure and the parameter W^*(ε) are studied, and a known result is improved. The main result is that for a Banach space X, if there is ε, where 0 < ε < 1/2, such that W^*(1 + ε) > ε/2 where W^*(1 + ε) = lim_→ε W^* (1 + ), then X has normal structure.     

Eigenvalues of the Laplacian of a graph

Let G be a finite undirected graph with no loops or multiple edges. We define the Laplacian matrix of G,Δ(G)by Δ_ij= degree of vertex i and Δ_ij-1 if there is an edge between vertex i and vertex j. In this paper we relate the structure of the graph G to the eigenvalues of A(G): in particular we prove that all the eigenvalues of Δ(G) are non-negative, less than or equal to the number of vertices, and less than or equal to twice the maximum vertex degree. Precise conditions for equality are given.