Sharp bounds for the number of 3‐independent partitions and the chromaticity of bipartite graphs

Given a graph G and an integer k ≥ 1, let α(G, k) denote the number of k‐independent partitions of G. Let ??^?s(p,q) (resp., ??₂^?s(p,q)) denote the family of connected (resp., 2‐connected) graphs which are obtained from the complete bipartite graph K_p,q by deleting a set of s edges, where p ≥ q ≥ 2. This paper first gives a sharp upper bound for α(G,3), where G ∈ ?? ^?s(p,q) and 0 ≤ s ≤ (p ? 1)(q ? 1) (resp., G ∈ ?? ₂^?s(p,q) and 0 ≤ s ≤ p + q ? 4). These bounds are then used to show that if G ∈ ?? ^?s(p,q) (resp., G ∈ ?? ₂^?s (p,q)), then the chromatic equivalence class of G is a subset of the union of the sets ??^?s_i(p+i,q?i) where max and s_i = s ? i(p?q+i) (resp., a subset of ??₂^?s(p,q), where either 0 ≤ s ≤ q ? 1, or s ≤ 2q ? 3 and p ≥ q + 4). By applying these results, we show finally that any 2‐connected graph obtained from K_p,q by deleting a set of edges that forms a matching of size at most q ? 1 or that induces a star is chromatically unique. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 48–77, 2001     

Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

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     

Iterated line graphs are maximally ordered

A graph G is k‐ordered if for every ordered sequence of k vertices, there is a cycle in G that encounters the vertices of the sequence in the given order. We prove that if G is a connected graph distinct from a path, then there is a number t_G such that for every t ≥ t_G the t‐iterated line graph of G, L^t (G), is (δ(L^t (G)) + 1)‐ordered. Since there is no graph H which is (δ(H)+2)‐ordered, the result is best possible. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 171–180, 2006     

The minimum degree of Ramsey‐minimal graphs

We write H → G if every 2‐coloring of the edges of graph H contains a monochromatic copy of graph G. A graph H is G‐minimal if H → G, but for every proper subgraph H′ of H, H′ ? G. We define s(G) to be the minimum s such that there exists a G‐minimal graph with a vertex of degree s. We prove that s(K_k) = (k ? 1)² and s(K_a,b) = 2 min(a,b) ? 1. We also pose several related open problems. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 167–177, 2007     

Building fences around the chromatic coefficients

Associated to each graph G is its chromatic polynomial f(G, t) and we associate to f(G, t) the sequence α (G) of the norms of its coefficients. A stringent partial ordering is established for such sequences. The main result is that for any graph G with q edges we have α (R_q) ≤ α (G) ≤ α (S_q), where R_q and S_q are specified graphs with q edges. This translates into a clearer view of allowable values and patterns in the chromatic coefficients. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 123–128, 1997     

Cycle lengths in graphs with large minimum degree

Our main result is the following theorem. Let k ≥ 2 be an integer, G be a graph of sufficiently large order n, and δ(G) ≥ n/k. Then:

• (i) G contains a cycle of length t for every even integer t ∈ [4, δ(G) + 1].
• (ii) If G is nonbipartite then G contains a cycle of length t for every odd integer t ∈ [2k ? 1, δ(G) + 1], unless k ≥ 6 and G belongs to a known exceptional class.

© 2006 Wiley Periodicals, Inc. J Graph Theory 52: 157–170, 2006     

Minimum degree thresholds for bipartite graph tiling

Given a bipartite graph H and a positive integer n such that v(H) divides 2n, we define the minimum degree threshold for bipartite H‐tiling, δ₂(n, H), as the smallest integer k such that every bipartite graph G with n vertices in each partition and minimum degree δ(G)≥k contains a spanning subgraph consisting of vertex‐disjoint copies of H. Zhao, Hladký‐Schacht, Czygrinow‐DeBiasio determined δ₂(n, K_{s, t}) exactly for all s?t and suffi‐ciently large n. In this article we determine δ₂(n, H), up to an additive constant, for all bipartite H and sufficiently large n. Additionally, we give a corresponding minimum degree threshold to guarantee that G has an H‐tiling missing only a constant number of vertices. Our δ₂(n, H) depends on either the chromatic number χ(H) or the critical chromatic number χ_cr(H), while the threshold for the almost perfect tiling only depends on χ_cr(H). These results can be viewed as bipartite analogs to the results of Kuhn and Osthus [Combinatorica 29 (2009), 65–107] and of Shokoufandeh and Zhao [Rand Struc Alg 23 (2003), 180–205]. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Edge disjoint Hamilton cycles in graphs

Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d _G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000     

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     

Partitioning complete multipartite graphs by monochromatic trees

The tree partition number of an r‐edge‐colored graph G, denoted by t_r(G), is the minimum number k such that whenever the edges of G are colored with r colors, the vertices of G can be covered by at most k vertex‐disjoint monochromatic trees. We determine t₂(K(n₁, n₂,…, n_k)) of the complete k‐partite graph K(n₁, n₂,…, n_k). In particular, we prove that t₂(K(n, m)) = ? (m‐2)/2ⁿ? + 2, where 1 ≤ n ≤ m. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 133–141, 2005     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

Connected subgraphs with small degree sums in 3‐connected planar graphs

It is well‐known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3‐connected planar graph has an edge xy such that deg(x) + deg (y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we show that, for a given positive integer t, every 3‐connected planar graph G with |V(G)| ≥ t has a connected subgraph H of order t such that Σ_x∈V(H) deg_G(x) ≤ 8t − 1. As a tool for proving this result, we consider decompositions of 3‐connected planar graphs into connected subgraphs of order at least t and at most 2t − 1. © 1999 John Wiley & Sons, Inc. J Graph Theory 30: 191–203, 1999     

Inequalities for the first‐fit chromatic number

The First‐Fit (or Grundy) chromatic number of G, written as χ_FF(G), is defined as the maximum number of classes in an ordered partition of V(G) into independent sets so that each vertex has a neighbor in each set earlier than its own. The well‐known Nordhaus‐‐Gaddum inequality states that the sum of the ordinary chromatic numbers of an n‐vertex graph and its complement is at most n + 1. Zaker suggested finding the analogous inequality for the First‐Fit chromatic number. We show for n ≥ 10 that ?(5n + 2)/4? is an upper bound, and this is sharp. We extend the problem for multicolorings as well and prove asymptotic results for infinitely many cases. We also show that the smallest order of C₄‐free bipartite graphs with χ_FF(G) = k is asymptotically 2k² (the upper bound answers a problem of Zaker [9]). © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 75–88, 2008     

Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_n,p (above the connectivity threshold) and for random regular graphs G_r,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t^* all components are of size O(log n). For G_n,p and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs D_n,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t^* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Non-traceability of large connected claw-free graphs

Let G be a connected claw-free graph on n vertices. Let ς₃(G) be the minimum degree sum among triples of independent vertices in G. It is proved that if ς₃(G) ≥ n − 3 then G is traceable or else G is one of graphs G_n each of which comprises three disjoint nontrivial complete graphs joined together by three additional edges which induce a triangle K₃. Moreover, it is shown that for any integer k ≥ 4 there exists a positive integer ν(k) such that if ς₃(G) ≥ n − k, n > ν(k) and G is non-traceable, then G is a factor of a graph G_n. Consequently, the problem HAMILTONIAN PATH restricted to claw-free graphs G = (V, E) (which is known to be NP-complete) has linear time complexity O(|E|) provided that ς₃(G) ≥ . This contrasts sharply with known results on NP-completeness among dense graphs. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 75–86, 1998     

An application of the regularity lemma in generalized Ramsey theory

Given graphs G and H, an edge coloring of G is called an (H,q)‐coloring if the edges of every copy of H ? G together receive at least q colors. Let r(G,H,q) denote the minimum number of colors in a (H,q)‐coloring of G. In 9 Erd?s and Gyárfás studied r(K_n,K_p,q) if p and q are fixed and n tends to infinity. They determined for every fixed p the smallest q (denoted by q_lin) for which r(K_n,K_p,q) is linear in n and the smallest q (denoted by q_quad) for which r(K_n,K_p,q) is quadratic in n. They raised the problem of determining the smallest q for which we have . In this paper by using the Regularity Lemma we show that if , then we have . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 39–49, 2003     

Modularity of Erdős‐Rényi random graphs

For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The modularity q^?(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q^?(G)<1. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erd?s‐Rényi random graph G_n,p with n vertices and edge‐probability p. Two key findings are that the modularity is 1+o(1) with high probability (whp) for np up to 1+o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)^?1/2 whp, in accord with a conjecture by Reichardt and Bornholdt in 2006. We also show that the modularity of a graph is robust to changes in a few edges, in contrast to the sensitivity of optimal vertex partitions.     

Constrained Ramsey numbers of graphs

Given two graphs G and H, let f(G,H) denote the minimum integer n such that in every coloring of the edges of K_n, there is either a copy of G with all edges having the same color or a copy of H with all edges having different colors. We show that f(G,H) is finite iff G is a star or H is acyclic. If S and T are trees with s and t edges, respectively, we show that 1+s(t?2)/2≤f(S,T)≤(s?1)(t²+3t). Using constructions from design theory, we establish the exact values, lying near (s?1)(t?1), for f(S,T) when S and T are certain paths or star‐like trees. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 1–16, 2003