An adaptive memory algorithm for the k-coloring problem

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory. At each iteration, the information contained in the central memory is used for producing an offspring solution which is then possibly improved using a local search algorithm. The so obtained solution is finally used to update the central memory. We describe in this paper an adaptive memory algorithm for the k-coloring problem. Computational experiments give evidence that this new algorithm is competitive with, and simpler and more flexible than, the best known graph coloring algorithms.     

On the equality of the partial Grundy and upper ochromatic numbers of graphs

A (proper) k-coloring of a graph G is a partition Π={V₁,V₂,…,V_k} of V(G) into k independent sets, called color classes. In a k-coloring Π, a vertex v∈V_i is called a Grundy vertex if v is adjacent to at least one vertex in color class V_j, for every j, j<i. A k-coloring is called a Grundy coloring if every vertex is a Grundy vertex. A k-coloring is called a partial Grundy coloring if every color class contains at least one Grundy vertex. In this paper we introduce partial Grundy colorings, and relate them to parsimonious proper colorings introduced by Simmons in 1982.     

Super-connectivity and super-edge-connectivity for some interconnection networks

Let G=(V,E) be a k-regular graph with connectivity κ and edge connectivity λ. G is maximum connected if κ=k, and G is maximum edge connected if λ=k. Moreover, G is super-connected if it is a complete graph, or it is maximum connected and every minimum vertex cut is {x|(v,x)E} for some vertex vV; and G is super-edge-connected if it is maximum edge connected and every minimum edge disconnecting set is {(v,x)|(v,x)E} for some vertex vV. In this paper, we present three schemes for constructing graphs that are super-connected and super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, möbius cubes, split-stars, and recursive circulant graphs.     

An upper bound for the adjacent vertex distinguishing acyclic edge chromatic number of a graph

A proper k-edge coloring of a graph G is called adjacent vertex distinguishing acyclic edge coloring if there is no 2-colored cycle in G and the color set of edges incident to u is not equal to the color set of edges incident to υ, where uυ ∈ E(G). The adjacent vertex distinguishing acyclic edge chromatic number of G, denoted by χ′ _aa (G), is the minimal number of colors in an adjacent vertex distinguishing acyclic edge coloring of G. In this paper we prove that if G(V, E) is a graph with no isolated edges, then χ′ _aa (G) ≤ 32Δ. Supported by the Natural Science Foundation of Gansu Province (3ZS051-A25-025)     

The b-Chromatic Number of Cubic Graphs

The b-chromatic number of a graph G is the largest integer k such that G admits a proper k-coloring in which every color class contains at least one vertex adjacent to some vertex in all the other color classes. It is proved that with four exceptions, the b-chromatic number of cubic graphs is 4. The exceptions are the Petersen graph, K _3,3, the prism over K ₃, and one more sporadic example on 10 vertices.     

Maximum-cover source location problems with objective edge-connectivity three

Given a graph G = (V, E), a set of vertices covers a vertex if the edge-connectivity between S and v is at least a given number k. Vertices in S are called sources. The maximum-cover source location problem, which is a variation of the source location problem, is to find a source set S with a given size at most p, maximizing the sum of the weight of vertices covered by S. In this paper, we show a polynomial-time algorithm for this problem in the case of k = 3 for a given undirected graph with a vertex weight function and an edge capacity function. Moreover, we show that this problem is NP-hard even if vertex weights and edge capacities are both uniform for general k.     

The k-Restricted Edge Connectivity of Balanced Bipartite Graphs

For a connected graph G = (V, E), an edge set S ì E{S\subset E} is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λ _k (G), is defined as the cardinality of a minimum k-restricted edge cut. For two disjoint vertex sets U₁,U₂ ì V(G){U_1,U_2\subset V(G)}, denote the set of edges of G with one end in U ₁ and the other in U ₂ by [U ₁, U ₂]. Define x_k(G)=min{|[U,V(G)\ U]|: U{\xi_k(G)=\min\{|[U,V(G){\setminus} U]|: U} is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ _k -optimal if λ _k (G) = ξ _k (G). A graph is said to be super-λ _k if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ _k -optimal or super-λ _k . Moreover, we demonstrate that our results are best possible.     

The special routes in plane graphs

Let plane undirected graph G = (V, E) be set of items of all manipulator possible trajectories. The problem is constructing of routes satisfying different restrictions. The restrictions can be classified as local and global. For local restrictions the next edge in a route is defined by the conditions set for current vertex or edge. Otherwise restriction is called global. Examples of local restrictions are straightforward paths; a route in which the next edge is defined by the given cycle order on the set of edges incident the current vertex; a route where some edges should be passed in predefined order. The example of global restriction is problem of constructing the cover with ordered enclosing. The paper presents some ways to formalize restrictions and also information about algorithms for constructing of Eulerian covering for plane graph by the sequence of allowed trails. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Degrees and choice numbers

The choice number ch(G) of a graph G=(V, E) is the minimum number k such that for every assignment of a list S(v) of at least k colors to each vertex v∈V, there is a proper vertex coloring of G assigning to each vertex v a color from its list S(v). We prove that if the minimum degree of G is d, then its choice number is at least (½−o(1))log₂ d, where the o(1)‐term tends to zero as d tends to infinity. This is tight up to a constant factor of 2+o(1), improves an estimate established by the author, and settles a problem raised by him and Krivelevich. © 2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 364–368, 2000     

Concise proofs for adjacent vertex-distinguishing total colorings

Let G=(V,E) be a graph and f:(V∪E)→[k] be a proper total k-coloring of G. We say that f is an adjacent vertex- distinguishing total coloring if for any two adjacent vertices, the set of colors appearing on the vertex and incident edges are different. We call the smallest k for which such a coloring of G exists the adjacent vertex-distinguishing total chromatic number, and denote it by χ_at(G). Here we provide short proofs for an upper bound on the adjacent vertex-distinguishing total chromatic number of graphs of maximum degree three, and the exact values of χ_at(G) when G is a complete graph or a cycle.     

Legal coloring of graphs

The following computational problem was initiated by Manber and Tompa (22nd FOCS Conference, 1981): Given a graphG=(V, E) and a real functionf:V→R which is a proposed vertex coloring. Decide whetherf is a proper vertex coloring ofG. The elementary steps are taken to be linear comparisons. Lower bounds on the complexity of this problem are derived using the chromatic polynomial ofG. It is shown how geometric parameters of a space partition associated withG influence the complexity of this problem. Existing methods for analyzing such space partitions are suggested as a powerful tool for establishing lower bounds for a variety of computational problems.     

A sufficient condition for planar graphs with maximum degree 8 to be 9-totally colorable

A total k-coloring of a graph G is a coloring of V(G) ∪ E(G) using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number χ'(G) is the smallest integer k such that G has a total k-coloring. It is known that if a planar graph G has maximum degree Δ≥ 9, then χ'(G) = Δ + 1. In this paper, we prove that if G is a planar graph with maximum degree 8 and without a fan of four adjacent 3-cycles, then χ'(G) = 9.     

Total coloring of embedded graphs of maximum degree at least ten

A total k-coloring of a graph G is a coloring of V(G) ∪ E(G) using k colors such that no two adjacent or incident elements receive the same color.The total chromatic number χ〃(G) is the smallest integer k such that G has a total k-coloring.In this paper,it is proved that the total chromatic number of any graph G embedded in a surface Σ of Euler characteristic χ(Σ)≥0 is Δ(G) + 1 if Δ(G)≥10,where Δ(G) denotes the maximum degree of G.     

A note on list improper coloring of plane graphs

A list-assignment L to the vertices of G is an assignment of a set L(v) of colors to vertex v for every v∈V(G). An (L,d)^∗-coloring is a mapping ? that assigns a color ?(v)∈L(v) to each vertex v∈V(G) such that at most d neighbors of v receive color ?(v). A graph is called (k,d)^∗-choosable, if G admits an (L,d)^∗-coloring for every list assignment L with |L(v)|≥k for all v∈V(G). In this note, it is proved that every plane graph, which contains no 4-cycles and l-cycles for some l∈{8,9}, is (3,1)^∗-choosable.     

Feasible Graphs and Colorings

The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective degree preserving correspondence between the set of k-colorings of G and the set of k-colorings of G′ and hence there are many examples of k-colorable polynomial time graphs with no recursive k-colorings. Moreover, even though every connected 2-colorable recursive graph is recursively 2-colorable, there are connected 2-colorable polynomial time graphs which have no primitive recursive 2-coloring. We also give some sufficient conditions which will guarantee that a polynomial time graph has a polynomial time or exponential time coloring.     

Bounds on the <Emphasis Type="Italic">k</Emphasis>-tuple domatic number of a graph

Let k be a positive integer, and let G be a simple graph with vertex set V (G). A vertex of a graph G dominates itself and all vertices adjacent to it. A subset S ⊆ V (G) is a k-tuple dominating set of G if each vertex of V (G) is dominated by at least k vertices in S. The k-tuple domatic number of G is the largest number of sets in a partition of V (G) into k-tuple dominating sets.     

A polynomial algorithm for finding (<Emphasis Type="Italic">g,f</Emphasis>)-colorings orthogonal to stars in bipartite graphs

Let G be a bipartite graph with vertex set V(G) and edge set E(G), and let g and f be two nonnegative integer-valued functions defined on V(G) such that g(x) ≤ f(x) for every vertex x of V(G). A (g, f)-coloring of G is a generalized edge-coloring in which each color appears at each vertex x at least g(x) and at most f(x) times. In this paper a polynomial algorithm to find a (g, f)-coloring of a bipartite graph with some constraints using the minimum number of colors is given. Furthermore, we show that the results in this paper are best possible.     

An ant colony algorithm for the pos/neg weighted p-median problem

Let a graph G = (V, E) with vertex set V and edge set E be given. The classical graph version of the p-median problem asks for a subset of cardinality p, so that the (weighted) sum of the minimum distances from X to all other vertices in V is minimized. We consider the semi-obnoxious case, where every vertex has either a positive or a negative weight. This gives rise to two different objective functions, namely the weighted sum of the minimum distances from X to the vertices in V\X and, differently, the sum over the minimum weighted distances from X to V\X. In this paper an Ant Colony algorithm with a tabu restriction is designed for both problems. Computational results show its superiority with respect to a previously investigated variable neighborhood search and a tabu search heuristic.This research has partially been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung.     

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.