# Immersion containment and connectivity in color-critical graphs.

1 Overview

The applications of graph coloring are legion. The usual goal, and the one we consider here, is to assign colors to vertices so that no two adjacent vertices are given the same color. Graph coloring has a long and storied history. The study of four-coloring planar graphs alone has generated interest for over 150 years [SK86]. Despite all this effort, graph coloring in general remains a notoriously difficult combinatorial problem.

Comparatively less is known about the immersion order and its applications. A pair of adjacent edges uv and vw, with u [nit equal to] v and v [not equal to] w, is lifted by deleting the edges uv and vw, and adding the edge uw. A graph H is said to be immersed in a graph G if and only if a graph isomorphic to H can be obtained from G by lifting pairs of edges and taking a subgraph. This notion is illustrated in Figure 1, which shows that [K.sub.4] is immersed in [K.sub.1] + [P.sub.5].

In the next section, we briefly survey some of the history behind the intriguing relationship between graph coloring and various forms of containment. Section 3 contains a few requisite mathematical preliminaries, foundational conjectures and initial observations. Here and elsewhere the central parameter is t, the number of colors in use. The main body of our work is contained in the subsequent two sections. In particular, we prove that, for arbitrary t [greater than or equal to] 5, every t-chromatic graph contains either an immersed [K.sub.t] or an immersed t-chromatic subgraph that is both 4-vertex connected and t-edge connected. This work, which is of special interest on its own, gives supporting evidence of our conjecture that every t-chromatic graph contains an immersed [K.sub.t].

[FIGURE 1 OMITTED]

2 Historical Context

The chromatic number of G, denoted by [chi](G), is the minimum number of colors required by G in any proper coloring of its vertices. It is tempting to try to associate x(G) with some sort of clique contained within G. After all, if G contains Kt as a subgraph(i), then it is easy to show that G can be colored with no fewer than t colors. To see that the presence of a Kt subgraph is not necessary, however, one needs only to observe that [C.sub.5], the cycle of order five, requires three colors yet does not contain K3 as a subgraph.

Nevertheless, perhaps some weaker form of Kt is present. One possibility is topological containment, in which taking subgraphs is augmented with removing subdivisions. An edge is subdivided when it is replaced by a path formed from two edges and an internal vertex of degree two; subdivision removal reverses this operation. For example, [C.sub.5] contains [K.sub.3] topologically. In the 1940s Hajos conjectured that if [chi](G) [greater than or equal to] t, then G contains a topological Kt [Haj61]. The conjecture is trivially true for t [less than or equal to] 3. In 1952 Dirac proved it true for t = 4 [Dir52]. It was not until Catlin's work in 1979 that Hajos' conjecture was finally settled, and negatively, with a family of counterexamples for t [greater than or equal to] 7 [Cat79]. Ironically, one such counterexample is the 15-vertex graph defined by the crossproduct of [C.sub.5] and [K.sub.3]. It requires eight colors but contains no topological [K.sub.8]. Subsequently, Erdos and Fajtlowicz were able to prove the rather surprising result that almost all graphs are counterexamples [EF81]. Thus Hajos' conjecture remains open only for t [member of] {5,6}.

Another possibility is the minor order, for which the allowable operations are taking subgraphs and contracting edges. The minor order is a generalization of the topological order, because subdivision removal is just a special case of edge contraction. Hadwiger conjectured in 1943 that, if [chi](G) [greater than or equal to] t, then G contains a Kt minor [Had43]. This conjecture equates to Hajos' conjecture for t [greater than or equal to] 4. Wagner proved in 1964 that, for t = 5, it is equivalent to the four color theorem [Wag64]. In 1993 Robertson, Seymour and Thomas proved it true for t = 6 [RST93]. Whether Hadwiger's conjecture holds true in general, however, has thus far not been decided. This is in spite of decades of research, hordes of supporting evidence and a multitude of results on many of its variants and restrictions [Bol78, Tof72, Tof95, Wes96]. Even the celebrated Graph Minor Theorem [RS04] appears to shed no particular light on this question, despite its extraordinary range of algorithmic applications [BL95]. As of this writing, a resolution of Hadwiger's conjecture seems distant.

In this paper we focus instead on the immersion order. Immersion containment is quite distinct from topological and minor containment. Recalling Figure 1, for example, we observe that [K.sub.4] is contained in [K.sub.1] + [P.sub.5] in neither the topological nor the minor order. Like the minor order, however, the immersion order is a generalization of the topological order. This is because subdivision removal is just a special case of lifting pairs of edges. Previous investigations into the immersion order have generally been conducted from a purely algorithmic standpoint. We refer the reader to [BGLR99, FL88, FL92, FL94, LP98] for examples and applications. In contrast, here we mainly consider structural issues. We establish compelling connections between graph coloring and the immersion order, which provides supporting evidence of our conjecture that [K.sub.t] is immersed in any t-chromatic graph(ii).

3 Preliminaries

We mainly restrict our attention to finite, simple undirected graphs (multiple edges and loops that may arise from lifting are irrelevant to coloring). G is said to be t-vertex-connected if at least t vertex-disjoint paths connect every pair of its vertices. Moreover, the cardinality of a smallest vertex cutset in G is equal to the largest t for which G is t-vertex-connected (unless G is a complete graph, which can have no vertex cutset). G is said to be t-edge-connected if at least t edge-disjoint paths connect every pair of its vertices, and the cardinality of a smallest edge cutset in G is equal to the largest t for which G is t-edge-connected.

We use [delta](G) to denote the minimum degree of a vertex of G. We use N(u) to denote the neighborhood of u. If [chi](G) [greater than or equal to] t, then G is said to be t-colorable. If [chi](G) = t, then G is said to be t-chromatic. If [chi](G) = t and [chi](H) < t for every proper subgraph H of G, then G is said to be t-color-critical. If G is t-color-critical, then it is easy to see that [delta](G) [greater than or equal to] t-1.

It is sometimes advantageous to select, restrict or manipulate colorings. For example, if G is t-chromatic but G-u is only (t-1)-chromatic, then it is possible to consider only colorings in which u is assigned a unique color. In fact, if G is t-color-critical, then for any vertex u there exists a coloring c in which c(u) = 1 and c(v) [not equal to] 1 for every vertex v [member of] G-u.

A t-coloring of G is realized by a map c from the vertices of G to the set {1,2, * * *, t} so that, if G contains the edge uv, then c(u) [not equal to] c(v). Given such a map, is used to denote the subgraph induced by the vertex set {u : c(u) [member of] {i, j}}. A path contained within is termed a Kempe chain [WT72], so-named in honor of the foundational work done on them by Kempe [Kem79]. Of course need not be connected, and so for any u [member of] [c.sub.ij] we employ [c.sub.ij](u) to denote the set {v : v resides in the same connected [c.sub.ij] component of [c.sub.ij] as does u}. Observe that, if {i, j} [not equal to] {k, l}, then [c.sub.ij] and [c.sub.kl] are edge-disjoint.

Although the immersion order is traditionally defined in terms of taking subgraphs and lifting pairs of edges, the fact that different Kempe chains are edge-disjoint make it helpful for us to utilize the following alternate characterization: H is immersed in G if and only if there exists an injection from the vertices of The conjecture was first published in the preliminary conference version of this paper at COCOON 2003. H to the vertices of G for which the images of adjacent elements of H are connected in G by edge-disjoint paths. Under such an injection, an image vertex is called a corner of H in G; all image vertices and their associated paths are collectively called a model of H in G.

Given the various connections between graph coloring, degrees and connectivity, and in turn the connections between connectivity and the immersion order, we seek to determine just how x(G) is related to immersion containment. Our efforts prompted us to set the stage for this with the following conjecture, which we formulated more than a decade ago.

Conjecture If [chi](G) [greater than or equal to] t, then Kt is immersed in G.

This conjecture motivates our work in the sequel. There we shall present what we believe is compelling evidence in its support. Our conjecture, like Hadwiger's, is trivially true for t [less than or equal to] 4. This is because the immersion order generalizes the topological order, for which Hajos' conjecture is long known to hold when t [less than or equal to] 4. Recently, Devos et al verified our conjecture for t [less than or equal to] 7 [DKMO10, [DDF.sup.+]]. The general case quite naturally appears to be much more difficult. Accordingly, our efforts in this paper focus mainly on global connectivity issues.

Before proceeding, we introduce a notion of immersion-criticality and show how it relates to the possible existence of counterexamples.

Definition G is t-immersion-critical if [chi](G) = t and [chi](H) < t whenever H is properly immersed in G.

Because [chi]([K.sub.t]) = t, any counterexample must either be t-immersion-critical or have properly immersed within it another t-immersion-critical counterexample. Similarly, any t-immersion-critical graph distinct from [K.sub.t] must be a counterexample. Thus our immersion-conjecture is equivalent to the statement that [K.sub.t] is the only t-immersion-critical graph for every t. Although we have thus far fallen short of establishing this one way or the other, we note that there are at most a finite number of them for each t. This follows easily from properties of well-quasi-orders and immersion order obstruction sets. We refer the reader unfamiliar with these concepts to [FL88, FL92, Kin93].

Graph connectivity has long been a central feature of attempts to settle Hadwiger's conjecture. G is said to be t-minor-critical (iii) [chi](G) = t and [chi](H) < t whenever H is a proper minor of G. [K.sub.t] is of course both (t-1)-vertex-connected and (t-1)-edge-connected. Thus, if any t-minor-critical graph is not as strongly connected, then Hadwiger's conjecture is false for all t' >[greater than or equal to] t. So suppose G denotes a t- minor-critical graph other than Kt (in which case the conjecture fails). Some 35 years ago, Mader [Mad68] showed that G must be at least 7-vertex-connected whenever t [greater than or equal to] 7. This provides evidence in support of our conjecture for t [member of] {7, 8}. A few years later [Tof72], Toft proved that G must also be t-edge-connected. This provides additional supporting evidence for all t. Very recently, Kawarabayashi has shown that G must be at least [t/3]-vertex-connected as well [Kaw07]. Following this approach, we study both the vertex and edge connectivity of t-immersion-critical graphs. We assume t [greater than or equal to] 8 unless stated otherwise. Kempe chains play a pivotal role in our investigation.

4 Vertex Connectivity of t-Immersion-Critical Graphs

Because they are t-color-critical, it is easy to see that t-immersion-critical graphs are 2-vertex-connected [Bol78]. We now establish that they must in fact be at least 4-vertex-connected. Our work linking coloring to the immersion order begins in earnest with Lemma 4. First, however, we present something of an introduction with three easy but useful lemmas about cutsets, paths and coloring. Lemmas 1 and 2 are probably well known, although they may not be formulated anywhere else in precisely the same way we state them in this treatment. Lemma 2, which we dub The Patching Lemma, is especially helpful. Lemma 3 is certainly well known, and mentioned in a variety of sources (see, for example, [Har69, Tof95, Wes96]). We include the proofs of these lemmas here both for completeness and, more importantly, to illustrate and clarify their utility in subsequent results.

Lemma 1 Let S denote a minimum-cardinality vertex cutset in a 2-vertex-connected graph G, and let C denote a connected component of G\S. Then any two elements of S must be connected by a path whose interior vertices lie completely within C.

Proof: Because G is 2-vertex-connected, [absolute value of S] [greater than or equal to] 2. Let a and b denote any two distinct elements of S. It must be that a is adjacent to some vertex u in C, since otherwise S is not minimal (S\{a} defines a vertex cutset of cardinality [absolute value of S] - 1). Similarly, it must be that b is adjacent to some vertex v in C .If u = v, then we are done. If u [not equal to] v, then the connectedness of C ensures that there is a subpath P from u to v lying completely within C. Thus au [union] P [union] vb is the desired path.

Two colorings are said to be equivalent if the partitions induced by their respective color classes are identical.

Lemma 2 (The Patching Lemma) Let S denote a vertex cutset of G, and let G1 and G2 denote a pair of induced subgraphs for which [G.sub.1] [union] [G.sub.2] = G and [G.sub.1] [intersection] [G.sub.2] = S. If [G.sub.1] and [G.sub.2] admit t-colorings whose restrictions to S are equivalent, then G is t-colorable.

Proof: Let S, G, [G.sub.1] and [G.sub.2]s be as defined in the statement of the lemma. Let c and d denote the specified t-colorings of [G.sub.1] and [G.sub.2], respectively. Modify one coloring, say d, by renaming its color classes so that each element of S is assigned the same integer under both colorings. Patched together, c and d now provide a t-coloring of G.

The Patching Lemma can be used to establish the following well-known fact.

Lemma 3 No vertex cutset of a t-color-critical graph can be a clique.

The preceding lemmas tell us a good deal about the make-up of vertex cutsets, and how they relate to coloring. Armed with this information, we are now able to argue more directly about vertex connectivity and the immersion order. To simplify matters, we shall adopt the following conventions for the remainder of this subsection:

- t is at least eight,

- G denotes a t-immersion-critical graph,

- S denotes a minimum-cardinality vertex cutset in G,

- C denotes a connected component of G\S,

- [G.sub.1] denotes the subgraph induced by C [union] S, and

- [G.sub.2] denotes G\C.

Lemma 4 Every t-immersion-critical graph is 3-vertex-connected.

Proof: Suppose otherwise, as witnessed by some G with S = {a, b}. We know from Lemma 3 that the edge ab is not present in G. Let i [member of] {1,2}. By Lemma 1, there must be a path, [P.sub.i], with endpoints a and b, whose vertices lie completely within [G.sub.i]. Lifting the edges of P3-i to form the single edge ab, and then taking the subgraph induced by the vertices of [G.sub.i], produces a graph H properly immersed in G. It follows that [H.sub.i] is (t-1)-colorable. Because ab is present in [H.sub.i], any such coloring of H assigns different colors to a and b. But [G.sub.i] is a subgraph of [H.sub.i]. Thus, there are (t-1)-colorings of [G.sub.1] and [G.sub.2] that each assign different colors to a and b. By the Patching Lemma, this ensures a (t-1)-coloring of G, a contradiction.

Lemma 5 If [absolute of S] = 3, then both [G.sub.1] and [G.sub.2] admit (t-1)-colorings that assign more than one color to the elements of S.

Proof: Let S = {u, v, w}, and consider the case for [G.sub.1]. By Lemma 1, there is a path between u and v in [G.sub.2]. Lifting this path and taking the subgraph induced by the vertices of G1 produces a graph H properly immersed in G. Because G is t-immersion-critical, and because H contains the edge uv, H admits a (t-1)-coloring that assigns different colors to u and v. As a subgraph of H, [G.sub.1] can likewise be colored. A symmetrical argument handles the case for [G.sub.2].

What we have really just shown is that if G is only 3-vertex-connected, then G1 admits a (t -- 1)coloring that assigns different colors to any fixed pair of elements of S. This raises the possibility that a single coloring of [G.sub.1] may suffice, simultaneously assigning different colors to all three elements of S. We now show that this cannot happen. It follows that the same must then be true for [G.sub.2].

Let a and b denote vertices of G, and let c denote a coloring of G in which c(a) = i = j = c(b). If a and b belong to the same connected component of , then they are connected by some Kempe chain Pj contained within [c.sub.ij]. In this event, we say that a and b are c-chained.

Lemma 6 If [absolute value of S] = 3, then neither G1 nor G2 admits a (t-1)-coloring that assigns three different colors to the elements of S.

Proof: Suppose otherwise, as witnessed by a (t-1)-coloring c of G1. Let S = {u, v, w} and assume, without loss of generality, that c(u) = 1, c(v) = 2 and c(w) = 3. Let d denote some (t-1)-coloring of [G.sub.2]. By Lemma 5 and the Patching Lemma, we may further assume, again without loss of generality, that d assigns exactly two colors to the elements of S, with d(u) = d(v). If u and v are not c-chained, then we can exchange colors 1 and 2 in [c.sub.12](v) to produce a (t-1)-coloring c' of G1 that assigns color 1 to both u and v and leaves the color of w set to 3. This means that the restrictions of c' and d to S are equivalent. But now, by the Patching Lemma, G is (t-1)-colorable, which is impossible.

Thus it must be that u and v are c-chained by some [P.sub.12] in [G.sub.1]. Lifting this chain and taking the subgraph induced by the vertices of [G.sub.2] produces a graph H properly immersed in G. H contains uv, and so must admit a (t-1) -coloring d' that assigns different colors to u and v. [G.sub.2] is likewise colored by d'. By the Patching Lemma, d' cannot assign a third color to w. So assume, again without loss of generality, that d'(w) = d'(u). If u and w are not c-chained, then (as in the previous argument) we can construct a (t-1)-coloring c' of G1 so that the restrictions of c" and d' to S are equivalent, which is impossible.

Thus it must be that u and w are c-chained by some P13 in G1. Because they are edge disjoint, [P.sub.12] and [P.sub.13] can be lifted simultaneously. Lifting these two chains and taking the subgraph induced by the vertices of [G.sub.2] produces a graph H' properly immersed in G. H' contains both uv and uw, and so must admit a (t-1)-coloring d" that assigns different colors to u and v and different colors to u and w. [G.sub.2] is likewise colored by d". By the Patching Lemma, d" cannot assign three colors to the elements of S. So it must be that d"(v) = d"(w). If v and w are not c-chained, then (as in the previous arguments) we can construct a (t -- 1)-coloring c"' of G1 so that the restrictions of c"' and d' to S are equivalent, which is impossible.

Thus it must be that v and w are c-chained by some P23 in G1. Because they are edge disjoint, P12, P13 and P23 can be lifted simultaneously. Lifting these three chains and taking the subgraph induced by the vertices of G2 produces a graph H" properly immersed in G. H" contains uv, uw and vw, and so must admit a (t-1)-coloring d"' that assigns three different colors to S. G2 is likewise colored by d"'. This means that the restrictions of c and d"' to S are equivalent, which is impossible, contradicting the supposition that c exists.

Bolstered by the preceding Lemmas, we are now ready to prove that minimum-cardinality vertex cutsets of t-immersion-critical graphs have at least four elements. The use of Kempe chains in Lemma 6 has been especially effective, so much so that we need only paths not chains in what follows.

Theorem 1 Every t-immersion-critical graph is 4-vertex-connected.

Proof: Suppose otherwise, as witnessed by some G with S = {u, v, w}. Let c and d denote (t-1)-colorings of G1 and G2, respectively. By Lemmas 5 and 6, we restrict our attention to the case in which both c and d assign exactly two colors to elements of S. Without loss of generality, assume c(u) = c(v) and d(u) = d(w). By Lemma 1, there is a path [P.sub.1] in [G.sub.1] whose endpoints are u and w. Similarly, there is a path P2 in G2 whose endpoints are u and v. Lifting [P.sub.i] and taking the graph induced by the vertices of G3-i produces a graph H3-i properly immersed in G. H1 contains uv, and so must admit a (t-1)coloring c' that assigns different colors to u and v. G1 is likewise colored by c'. By Lemma 6, c' cannot assign a third color to w. Lest the restrictions of c' and d to S be equivalent, it must be that c'(w) = c'(v) . H2 contains uw, and so must admit a (t-1)-coloring d' that assigns different colors to u and w. [G.sub.2] is likewise colored by d'. By Lemma 6, d' cannot assign a third color to v. But if d'(v) = d'(u), then the restrictions of c and d' to S are equivalent. And if d'(v) = d'(w), then the restrictions of c' and d' to S are equivalent. Thus, under some pair of colorings of [G.sub.1] and [G.sub.2], the Patching Lemma ensures that G is (t-1)-colorable, a contradiction.

5 Edge Connectivity

Because the immersion order includes the taking of subgraphs, we know that t-immersion-critical graphs are also t-color-critical. From the work of [Tof74] it follows that they are (t-1) -edge-connected. We now show that any t-immersion-critical graph other than [K.sub.t] is in fact t-edge-connected. We begin a pair of well-known observations (see, for example, [Wes96]).

Observation 1 A minimum-cardinality edge cutset separates a graph into exactly two connected components.

Observation 2 If H is obtained by deleting the edge uv from a t-color-critical graph, then H is (t-1)-colorable and, under any (t-1)-coloring, u and v are assigned the same color.

The significance of Observation 2 rests with the next lemma, which plays an essential role in our edge-connectivity arguments. This lemma is probably also well known, although it may not be formulated elsewhere in exactly the same way we state it here.

Lemma 7 Let H be obtained by deleting the edge uv froma t-color-critical graph. Let c denotea (t -- 1)coloring of H with c(u) = c(v) = 1. Then v [member of] [c.sub.1i](u) for all i [member of] {2, 3, cdots,t -- 1}.

Proof: Let H and c be defined as stated. Suppose the lemma is false, as witnessed by some i with v [member of] [c.sub.1i](u). Exchanging colors 1 and i in [c.sub.1i](u) produces c', another (t-1)-coloring of H. But then u and v are assigned different colors under c', which is impossible.

Aided by this information about color-criticality, we are now able to argue more directly about edge connectivity and the immersion order. We shall adopt the following conventions for the remainder of this subsection:

- t is at least eight,

- G denotes a t-immersion-critical graph,

- S denotes a minimum-cardinality edge cutset in G,

- [C.sub.1] and [C.sub.2] denote the two connected components of G\S,

- [S.sub.1] and [S.sub.2] denote the endpoints of S contained in [C.sub.1] and [C.sub.2], respectively,

- uv denotes an element of S, with u [member of] [S.sub.1] and v [member of] [S.sub.2], and

- H denotes G\{uv}.

Lemma 8 If G is not t-edge-connected, then every (t-1)-coloring of H assigns either one color to [S.sub.1] and all t-1 colors to [S.sub.2] or vice versa.

Proof: Suppose G is not t-edge-connected. We know from [Tof74] that [absolute value of S] = t-1. Let c denote a (t-1)- coloring of H with c(u) = c(v) = 1. Lemma 7 ensures that v [member of] [c.sub.1i](u) for all i [member of] {2,3, * * * ,t-1}. Therefore u and v are the endpoints of t-2 Kempe chains, where each chain is contained within [c.sub.1i](u) for some i. The chains are edge disjoint, and so each contains at least one distinct element of S' = S\{uv}. Thus there is a one-to-one correspondence between chains and elements of S'. This means that every element of S' has an endpoint assigned color 1 by c. If c assigns only color 1 to S1, then it must assign all t-1 colors to [S.sub.2]. Similarly, if c assigns all t-1 colors to [S.sub.1], then it must assign only color 1 to [S.sub.2].

The only remaining case to consider occurs if c assigns more than one but fewer than t -- 1 colors to S1. To show that this cannot happen, we now proceed by contradiction, and suppose S1 contains vertex w assigned color i, but no vertex assigned color j, where {i, j} [subset or equal to] {2,3, * * * ,t -- 1}. It must be that [c.sub.ij] (w) is completely contained within [C.sub.1]. We exchange colors i and j in (w) to produce c', another (t-1)-coloring of H with c'(u) = c'(v) = 1. By this construction, c' assigns color j to endpoints of two different elements of S', and accordingly assigns color i to the endpoint of no element of S'. We conclude that v [member of] [c'.sub.1i](u), contradicting Lemma 7.

Theorem 2 Any t-immersion-critical graph other than [K.sub.t] is t-edge-connected.

Proof: Suppose otherwise, as witnessed by some G, not isomorphic to [K.sub.t], that is only (t-1)-edge-connected. We apply Lemma 8 and, without loss of generality, let c denote a (t-1)-coloring of H that assigns color 1 to [S.sub.1] [union] {v}. Thus all t-1 colors are assigned to [S.sub.2], and we index the elements of [S.sub.2] by {v = [v.sub.1], [v.sub.2], * * *, [v.sub.t-1]}, where c([v.sub.i]) = i.

Let i and j denote distinct elements of {1,2, *** , t - 1}. It must be that [v.sub.i] belongs to [c.sub.ij] ([v.sub.j]), since otherwise we can exchange colors i and j in ([v.sub.i]) to produce a (t -- 1)-coloring of H in which the elements of [S.sub.2] are assigned t-2 colors, thereby contradicting Lemma 8. It follows that [v.sub.i] and [v.sub.i] are the endpoints of a Kempe chain contained within ([v.sub.i]). Moreover, even if i or j is 1, the elements of [S.sub.1] are excluded from this chain. Therefore the chain is completely contained within C2. Because such a chain exists for each pair of vertices in [S.sub.2], and because the chains are edge disjoint, [K.sub.t-1] is immersed in [C.sub.2] using a model whose corners are the elements of [S.sub.2].

Now let i denote an element of {2, *** ,t-1}. From the proof of Lemma 8, we know that u and v are the endpoints of a Kempe chain containing [v.sub.i]. This means that u and [v.sub.i] are the endpoints of a subchain completely contained within [C.sub.1] [union] S. Because such a chain exists for each vertex in S2\{v}, because the chains are edge disjoint, and because uv [member of] G, [K.sub.t] is immersed in G using a model whose corners are {u} [union] [S.sub.2]. This is the desired contradiction.

Corollary 1 If G is t-immersion-critical and not [K.sub.t], then [delta](G)[greater than or equal to]t.

Proof: Immediate from Theorem 2 and the fact that [delta](G) is an upper bound on G's edge connectivity.

Corollary 2 If G is t-color-critical with a vertex u of degree t -- 1, then Kt is immersed in G via a model whose corners are {u} U N(u).

Proof: Follows from the proof of Theorem 2 by letting S be the set of edges incident on u.

References

[BGLR99] H. D. Booth, R. Govindan, M. A. Langston, and S. Ramachandramurthi. Sequential and parallel algorithms for K4 immersion testing. J. of Algorithms, 30:344--378, 1999.

[BL95] D. Bienstock and M. A. Langston. Algorithmic implications of the graph minor theorem. In M. O. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, editors, Handbook of Operations Research and Management Science: Network Models, pages 481--502. North-Holland, 1995.

[Bol78] B. Bollobas. Extremal Graph Theory. Academic Press, 1978.

[Cat79] P. A. Catlin. Hajos graph-coloring conjecture: variation and counterexamples. J. of Combinatorial Theory, Series B, 26:268-274, 1979.

[DD[F.sup.+]] M. DeVos, Z. Dvorak, J. Fox, J. McDonald, B. Mohar, and D. Scheide. Minimum degree condition forcing complete graph immersion. (http://arxiv.org/abs/1101.2630).

[Dir52] G. A. Dirac. A property of 4-chromatic graphs and some remarks on critical graphs. J. London Math. Soc., 27:85-92, 1952.

[DKMO10] M. Devos, K. Kawarabayashi, B. Mohar, and H. Okamura. Immersing small complete graphs. Ars Mathematica Contemporanea, 3:139-146, 2010.

[EF81] P. Erdos and S. Fajtlowicz. On the conjecture of Hajos. Combinatorica, 1:141--143, 1981.

[FL88] M. R. Fellows and M. A. Langston. Nonconstructive tools for proving polynomial-time decidability. J. of the ACM, 35:727-739, 1988.

[FL92] M. R. Fellows and M. A. Langston. On well-partial-order theory and its application to combinatorial problems of VLSI design. SIAM J. on Discrete Mathematics, 5:117--126, 1992.

[FL94] M. R. Fellows and M. A. Langston. On search, decision and the efficiency of polynomial-time algorithms. J. of Computer and Systems Sciences, 49:769--779, 1994.

[Haj61] G. Hajos. Uber eine Konstruktion nicht n-farbbarer Graphen. Wiss. Z. Martin Luther Univ. HalleWittenberg, Math. Naturwiss. Reihe, 10:116-117, 1961.

[Har69] F. Harary. Graph Theory. Addison-Wesley, 1969.

[Kaw07] K. Kawarabayashi. On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture. J. of Combinatorial Theory, Series B, 97(1):144-150, 2007.

[Kem79] A. B. Kempe. How to color a map with four colours without coloring adjacent districts the same color. Nature, 20:275, 1879.

[Kin93] N. G. Kinnersley. Immersion order obstruction sets. Congressus Numerantium, 98:113-123, 1993.

[LP98] M. A. Langston and B. C. Plaut. Algorithmic applications of the immersion order. Discrete Mathematics, 182:191-196, 1998.

[RS04] N. Robertson and P. D. Seymour. Graph minors XX: Wagner's conjecture. J. of Combinatorial Theory, Series B, 92(2), 2004.

[RST93] N. Robertson, P. D. Seymour, and R. Thomas. Hadwiger's conjecture for K6-free graphs. Combinatorica, 13:279-361, 1993.

[SK86] T. L. Saaty and P. C. Kainen. The Four-Color Problem. Dover Publications, Inc., 1986.

[Tof72] B. Toft. On separating sets of edges in contraction-critical graphs. Math. Ann., 196:129--147, 1972.

[Tof74] B. Toft. On critical subgraphs of colour critical graphs. Discrete Mathematics, 7:377-392, 1974.

[Tof95] B. Toft. Colouring, stable sets and perfect graphs. In R. Graham, M. Grotschel, and L. Lovasz, editors, Handbook of Combinatorics, volume 2, chapter 4, pages 233--288. Elsevier Science B.V., 1995.

[Wag64] K. Wagner. Beweis einer Abschwachung der Hadwiger-Vermutung. Math. Ann., 153:139-141, 1964.

[Wes96] D. B. West. Introduction to Graph Theory. Prentice Hall, 1996.

[WT72] H. Whitney and W. T. Tutte. Kempe chains and the four colour problem. Utilitas Math., 2:241-281, 1972.

(i) Of course what we really mean is that G contains a subgraph isomorphic to Kt. We shall henceforth adopt this slight abuse of terminology, dropping the cumbersome reference to isomorphism as long as it creates no confusion or ambiguity.

(ii) The conjecture was first published in the preliminary conference version of this paper at COCOON 2003.

(iii) In the literature, this notion has sometimes been termed t-contraction-critical.

Faisal N. Abu-Khzam (1) ([section]) and Michael A. Langston (2) ([paragraph])

(1) Department of Computer Science and Mathematics, Lebanese American University, Beirut, Lebanon

(2) Department of Electrical Engineering and Computer Science, University of Tennessee, Knoxville TN, USA

([dagger]) This research has been supported in part by the National Science Foundation under grants EIA-9972889 and CCR- 0075792, by the Office of Naval Research under grant N00014-01-1-0608, by the Department of Energy under contract DE-AC05- 00OR22725, and by the Tennessee Center for Information Technology Research under award E01-0178-081.

([double dagger]) A preliminary version of a portion of this paper was presented at the Ninth International Conference on Computing and Combinatorics, held in Big Sky, Montana, in July 2003.

([section]) Email: faisal.abukhzam@lau.edu.lb

([paragraph]) Email: langston@eecs.utk.edu

received 10th January 2012, accepted 19th September 2012.
Author: Printer friendly Cite/link Email Feedback Abu-Khzam, Faisal N.; Langston, Michael A. Discrete Mathematics and Theoretical Computer Science Report 7IRAN Jun 1, 2012 5785 Random Cayley digraphs of diameter 2 and given degree. Acyclic chromatic index of fully subdivided graphs and Halin graphs. Algorithms Graph theory