On the acyclic choosability of graphs

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is L‐list colorable if for a given list assignment L = {L(v): v ∈ V}, there exists a proper coloring c of G such that c (v) ∈ L(v) for all v ∈ V. If G is L‐list colorable for every list assignment with |L (v)| ≥ k for all v ∈ V, then G is said k‐choosable. A graph is said to be acyclically k‐choosable if the obtained coloring is acyclic. In this paper, we study the links between acyclic k‐choosability of G and Mad(G) defined as the maximum average degree of the subgraphs of G and give some observations about the relationship between acyclic coloring, choosability, and acyclic choosability. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 281–300, 2006     

Cycles containing all vertices of maximum degree

For a graph G and an integer k, denote by V_k the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |V_k| ≤ k, then G has a cycle containing all vertices of V_k. It is shown that the upper bound k on |V_k| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |V_k| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 John Wiley & Sons, Inc.     

On low bound of degree sequences of spanning trees in K-edge-connected graphs

A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A d_k-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, d_T(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d_k-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998     

Acyclic 5‐choosability of planar graphs without small cycles

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L = {L(v): v: ∈ V}, there exists a proper acyclic coloring ? of G such that ?(v) ∈ L(v) for all v ∈ V. If G is acyclically L‐list colorable for any list assignment with |L (v)|≥ k for all v ∈ V, then G is acyclically k‐choosable. In this article, we prove that every planar graph G without 4‐ and 5‐cycles, or without 4‐ and 6‐cycles is acyclically 5‐choosable. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 245–260, 2007     

Centers to centroids in graphs

For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize e_s(u) = max {d(u, v): v ∈ S} and d_s(u) = ∑_u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let r_k(u) = max {∑_s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which r_k(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.     

Brooks-type theorems for choosability with separation

We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ∈ V such that |L(v)| = p for all v ∈ V and |L(u) ∩ L(v)| ≤ c for all uv ∈ E, is it possible to find a “list coloring,” i.e., a color f(v) ∈ L(v) for each v ∈ V, so that f(u) ≠ f(v) for all uv ∈ E? We prove that every of maximum degree Δ admits a list coloring for every such list assignment, provided p ≥ . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = K_n (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)) . For planar graphs and c = 1, lists of length 4 suffice. ˜© 1998 John Wiley & Sons, Inc. J Graph Theory 27: 43–49, 1998     

List Colorings of K5‐Minor‐Free Graphs With Special List Assignments

The following question was raised by Bruce Richter. Let G be a planar, 3‐connected graph that is not a complete graph. Denoting by d(v) the degree of vertex v, is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), 6} for all v∈V(G)? More generally, we ask for which pairs (r, k) the following question has an affirmative answer. Let r and k be the integers and let G be a K₅‐minor‐free r‐connected graph that is not a Gallai tree (i.e. at least one block of G is neither a complete graph nor an odd cycle). Is G L‐list colorable for every list assignment L with |L(v)| = min{d(v), k} for all v∈V(G)? We investigate this question by considering the components of G[S_k], where S_k: = {v∈V(G)|d(v)8k} is the set of vertices with small degree in G. We are especially interested in the minimum distance d(S_k) in G between the components of G[S_k]. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:18–30, 2012     

Some results on generalized exponents

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ⁺(G) = max{d⁺(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)² + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998     

Insertible vertices,neighborhood intersections,and hamiltonicity

Let G be a simple undirected graph of order n. For an independent set S ? V(G) of k vertices, we define the k neighborhood intersections S_i = {v ? V(G)&#92;S|N(v) ∩ S| = i}, 1 ≦ i ≦ k, with s_i = |S_i|. Using the concept of insertible vertices and the concept of neighborhood intersections, we prove the following theorem.     

Acyclic 6-choosability of planar graphs without adjacent short cycles

A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ(v)∈L(v)for all v∈V.If G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).     

The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.     

Every toroidal graph is acyclically 8-choosable

A proper coloring of a graphG is acyclic if G contains no 2-colored cycle.A graph G is acyclically L-list colorable if for a given list assignment L={L(v):v∈V(G)},there exists a proper acyclic coloringφof G such thatφ(v)∈L(v)for all v∈V(G).If G is acyclically L-list colorable for any list assignment L with|L(v)|≥k for all v∈V(G),then G is acyclically k-choosable.In this article,we prove that every toroidal graph is acyclically 8-choosable.     

Labeling graphs with two distance constraints

Given a graph G and integers p,q,d₁ and d₂, with p>q, d₂>d₁?1, an L(d₁,d₂;p,q)-labeling of G is a function f:V(G)→{0,1,2,…,n} such that |f(u)−f(v)|?p if d_G(u,v)?d₁ and |f(u)−f(v)|?q if d_G(u,v)?d₂. A k-L(d₁,d₂;p,q)-labeling is an L(d₁,d₂;p,q)-labeling f such that max_v∈V(G)f(v)?k. The L(d₁,d₂;p,q)-labeling number ofG, denoted by , is the smallest number k such that G has a k-L(d₁,d₂;p,q)-labeling. In this paper, we give upper bounds and lower bounds of the L(d₁,d₂;p,q)-labeling number for general graphs and some special graphs. We also discuss the L(d₁,d₂;p,q)-labeling number of G, when G is a path, a power of a path, or Cartesian product of two paths.     

List circular coloring of trees and cycles

Suppose G=(V, E) is a graph and p ≥ 2q are positive integers. A (p, q)‐coloring of G is a mapping ?: V → {0, 1, …, p‐1} such that for any edge xy of G, q ≤ |?(x)‐?(y)| ≤ p‐q. A color‐list is a mapping L: V → ({0, 1, …, p‐1}) which assigns to each vertex v a set L(v) of permissible colors. An L‐(p, q)‐coloring of G is a (p, q)‐coloring ? of G such that for each vertex v, ?(v) ∈ L(v). We say G is L‐(p, q)‐colorable if there exists an L‐(p, q)‐coloring of G. A color‐size‐list is a mapping ? which assigns to each vertex v a non‐negative integer ?(v). We say G is ?‐(p, q)‐colorable if for every color‐list L with |L(v)| = ?(v), G is L‐(p, q)‐colorable. In this article, we consider list circular coloring of trees and cycles. For any tree T and for any p ≥ 2q, we present a necessary and sufficient condition for T to be ?‐(p, q)‐colorable. For each cycle C and for each positive integer k, we present a condition on ? which is sufficient for C to be ?‐(2k+1, k)‐colorable, and the condition is sharp. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 249–265, 2007     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

Long paths through four vertices in a 2‐connected graph

Let G be a 2‐connected graph, let u and v be distinct vertices in V(G), and let X be a set of at most four vertices lying on a common (u, v)‐path in G. If deg(x) ≥ d for all x ∈ V(G) \ {u, v}, then there is a (u, v)‐path P in G with X ⊂ V(P) and |E(P)| ≥ d. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 55–65, 2000     

Some new perfect Steiner triple systems

In a Steiner triple system STS(v) = (V, B), for each pair {a, b} ⊂ V, the cycle graph G_a,b can be defined as follows. The vertices of G_a,b are V \ {a, b, c} where {a, b, c} ∈ B. {x, y} is an edge if either {a, x, y} or {b, x, y} ∈ B. The Steiner triple system is said to be perfect if the cycle graph of every pair is a single (v − 3)-cycle. Perfect STS(v) are known only for v = 7, 9, 25, and 33. We construct perfect STS (v) for v = 79, 139, 367, 811, 1531, 25771, 50923, 61339, and 69991. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 327–330, 1999     

Matching properties in connected domination critical graphs

A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γ_c(G) denote the size of any smallest connected dominating set in G. A graph G is k-γ-connected-critical if γ_c(G)=k, but if any edge is added to G, then γ_c(G+e)?k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph G was defined to be k-critical if the domination number of G is k, but if any edge is added to G, the domination number falls to k-1.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G), bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G) or, more generally, k-factor-critical if, for every set S⊆V(G) with |S|=k, the graph G-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if |V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].].     

Long cycles passing through a specified path in a graph

For a graph G and an integer k ≥ 1, let ς_k(G) = d_G(v_i): {v₁, …, v_k} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς₂(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998