On H‐immersions

For a fixed multigraph H, possibly containing loops, with V(H) = {h₁,…, h_k}, we say a graph G is H‐linked if for every choice of k vertices v₁,…,v_k in G, there exists a subdivision of H in G such that v_i represents h_i (for all i). An H‐immersion in G is similar except that the paths in G, playing the role of the edges of H, are only required to be edge disjoint. In this article, we extend the notion of an H‐linked graph by determining minimum degree conditions for a graph G to contain an H‐immersion with a bounded number of vertex repetitions on any choice of k vertices. In particular, we extend results found in [2,3,5]. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 245–254, 2008     

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     

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     

Ore‐type degree conditions for a graph to be H‐linked

Given a fixed multigraph H with V(H) = {h₁,…, h_m}, we say that a graph G is H‐linked if for every choice of m vertices v₁, …, _vm in G, there exists a subdivision of H in G such that for every i, v_i is the branch vertex representing h_i. This generalizes the notion of k‐linked graphs (as well as some other notions). For a family of graphs, a graph G is ‐linked if G is H‐linked for every . In this article, we estimate the minimum integer r = r(n, k, d) such that each n‐vertex graph with is ‐linked, where is the family of simple graphs with k edges and minimum degree at least . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 14–26, 2008     

K‐linked graphs with girth condition

Recently, Mader [ 7 ] proved that every 2k‐connected graph with girth g(G) sufficiently large is k‐linked. We show here that g(G ≥ 11 will do unless k = 4,5. If k = 4,5, then g(G) ≥ 19 will do. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 48–50, 2004     

Implications among linkage properties in graphs

Given a graph H with vertices w₁, …, w_m, a graph G with at least m vertices is H‐linked if for every choice of vertices v₁, …, v_m in G, there is a subdivision of H in G such that v_i is the branch vertex representing w_i (for all i ). This concept generalizes the notions of k‐linked, k‐connected, and k‐ordered graphs. For graphs H₁ and H₂ with the same order that are not contained in stars, the property of being H₁‐linked implies that of being H₂‐linked if and only if H₂?H₁. The implication also holds when H₁ is obtained from H₂ by replacing an edge xy with an edge from y to a new vertex x′. Other instances of nonimplication are obtained, using a lemma that the number of vertices appearing in minimum vertex covers of a graph G is at most the vertex cover number plus the size of a maximum matching. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 327‐337, 2009     

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     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

Bi‐arc graphs and the complexity of list homomorphisms

Given graphs G, H, and lists L(v) ? V(H), v ε V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) → V(H) such that uv ε E(G) implies f(u)f(v) ε E(H), and f(v) ε L(v) for all v ε V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) ? V(H), v ε V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003     

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     

Connectivity keeping paths in k‐connected graphs

A result of G. Chartrand, A. Kaugars, and D. R. Lick [Proc Amer Math Soc 32 (1972), 63–68] says that every finite, k‐connected graph G of minimum degree at least ?3k/2? contains a vertex x such that G?x is still k‐connected. We generalize this result by proving that every finite, k‐connected graph G of minimum degree at least ?3k/2?+m?1 for a positive integer m contains a path P of length m?1 such that G?V(P) is still k‐connected. This has been conjectured in a weaker form by S. Fujita and K. Kawarabayashi [J Combin Theory Ser B 98 (2008), 805–811]. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 61–69, 2010.     

List multicoloring problems involving the k‐fold Hall numbers

We show that the four‐cycle has a k‐fold list coloring if the lists of colors available at the vertices satisfy the necessary Hall's condition, and if each list has length at least ?5k/3?; furthermore, the same is not true with shorter list lengths. In terms of h^(k)(G), the k ‐fold Hall number of a graph G, this result is stated as h^(k)(C₄)=2k??k/3?. For longer cycles it is known that h^(k)(C_n)=2k, for n odd, and 2k??k/(n?1)?≤h^(k)(C_n)≤2k, for n even. Here we show the lower bound for n even, and conjecture that this is the right value (just as for C₄). We prove that if G is the diamond (a four‐cycle with a diagonal), then h^(k)(G)=2k. Combining these results with those published earlier we obtain a characterization of graphs G with h^(k)(G)=k. As a tool in the proofs we obtain and apply an elementary generalization of the classical Hall–Rado–Halmos–Vaughan theorem on pairwise disjoint subset representatives with prescribed cardinalities. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 16–34, 2010.     

On the structure of graphs with a unique k‐factor

In this paper we study the structure of graphs with a unique k‐factor. Our results imply a conjecture of Hendry on the maximal number m (n,k) of edges in a graph G of order n with a unique k‐factor: For we prove and construct all corresponding extremal graphs. For we prove . For n = 2kl, l ∈ ℕ, this bound is sharp, and we prove that the corresponding extremal graph is unique up to isomorphism. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 227–243, 2000     

Clique‐inverse graphs of K3‐free and K4‐free graphs

The clique graph K(G) of a given graph G is the intersection graph of the collection of maximal cliques of G. Given a family ℱ of graphs, the clique‐inverse graphs of ℱ are the graphs whose clique graphs belong to ℱ. In this work, we describe characterizations for clique‐inverse graphs of K₃‐free and K₄‐free graphs. The characterizations are formulated in terms of forbidden induced subgraphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 257–272, 2000     

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     

Highly edge‐connected detachments of graphs and digraphs

Let G = (V,E) be a graph or digraph and r : V → Z₊. An r‐detachment of G is a graph H obtained by ‘splitting’ each vertex ν ∈ V into r(ν) vertices. The vertices ν₁,…,ν_r(ν) obtained by splitting ν are called the pieces of ν in H. Every edge uν ∈ E corresponds to an edge of H connecting some piece of u to some piece of ν. Crispin Nash‐Williams 9 gave necessary and sufficient conditions for a graph to have a k‐edge‐connected r‐detachment. He also solved the version where the degrees of all the pieces are specified. In this paper, we solve the same problems for directed graphs. We also give a simple and self‐contained new proof for the undirected result. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 67–77, 2003     

Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001     

Det‐extremal cubic bipartite graphs

Let G be a connected k–regular bipartite graph with bipartition V(G) = X ∪ Y and adjacency matrix A. We say G is det‐extremal if per (A) = |det(A)|. Det–extremal k–regular bipartite graphs exist only for k = 2 or 3. McCuaig has characterized the det‐extremal 3‐connected cubic bipartite graphs. We extend McCuaig's result by determining the structure of det‐extremal cubic bipartite graphs of connectivity two. We use our results to determine which numbers can occur as orders of det‐extremal connected cubic bipartite graphs, thus solving a problem due to H. Gropp. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 50–64, 2003     

The n‐ordered graphs: A new graph class

For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R⁽ⁿ⁾, which we name the infinite random n‐ordered graphs. The graphs R⁽ⁿ⁾ play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R⁽ⁿ⁾ as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R⁽ⁿ⁾ are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R⁽ⁿ⁾. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009