On (k, d)-Colorings and Fractional Nowhere Zero Flows

Luis A. Goddyn^{∗}

Department of Mathematics and Statistics Simon Fraser University Burnaby, BC

Michael Tarsi

Computer Science Department School of Mathematical Sciences Tel-Aviv University, 69978 Israel

Cun-Quan Zhang^{†}

Department of Mathematics West Virginia University Morgantown, WV

July 22, 1993

Abstract The concepts of (k, d)-coloring and the star chromatic number, studied by Vince, by Bondy and Hell, and by Zhu are shown to reflect the cographic instance of a wider concept, that of fractional nowhere-zero flows in regular matroids.

1 Introduction

Vince [12] introduced the following generalization of chromatic number.

Definition 1.1 A (k, d)-coloring of a graph G is a function c : V (G) → Z_{k} such that for every xy ∈ E(G), |c(x) − c(y)| ≥ d. (Here, Z_{k} denotes the cyclic group of residues mod k, and |a| is the smaller of the two integers a and k − a.) The star chromatic number, χ^{∗}(G), is the infimum of k/d over all (k, d)-colorings of G.

Vince proved, by means of analytical arguments, that this infimum is a minimum (and hence rational). He also proved that for every k, d such that k/d ≥ χ^{∗}(G), there exists a (k, d)-coloring of G. Setting d = 1 we have that the chromatic number of G is χ(G) = ⌈χ^{∗}(G)⌉. Later, Bondy and Hell [1] improved Vince’s result by giving a purely combinatorial proof. A further study and an alternate definition of χ^{∗}(G) in terms of homomorphisms into intervals of a unit circle appear in [14]. The purpose of this note is to show that (k, d)-colorings are an instance of the more general concept of fractional nowhere-zero flows in regular matroids.

∗Supported by the National Sciences and Engineering Research Council operating grant #A-4699. †Partially supported under NSF grant DMS-9306379.

2 Fractional Flows in Graphs

It is helpful to introduce the notion of fractional flows in graphs before considering the general matroidal case. Let k be a positive integer. A k-flow in a graph G is an orientation ω(G) together with a function f : E(G) → {0, ±1, ±2, …, ±(k − 1)} such that the net flow ∑_{vu∈δ^{+}(v)} f(vu) − ∑_{uv∈δ^{−}(v)} f(uv) is zero for each v ∈ V (G). The flow index, ξ(G) is the least k for which G has a nowhere-zero k-flow (that is, f(e) ≠ 0, for all e ∈ E(G)). This parameter has been studied by many authors (see [8] for a thorough review). We generalize this notion with the following.

Definition 2.1 A (k, d)-flow in a graph G is a k-flow (ω(G), f) such that the range of f is contained in {±d, ±(d + 1), …, ±(k − d)}. The star flow index ξ^{∗}(G) is the infimum of k/d over all (k, d)-flows in G.

Thus, a (k, 1)-flow is the same as a nowhere-zero k-flow. We shall see that, analogously to (k, d)- colorings, the infimum in Definition 2.1 is a minimum, and G has a (k, d)-flow whenever k/d ≥ ξ^{∗}(G), and thus that ξ(G) = ⌈ξ^{∗}(G)⌉.

It is well known that, in the setting of matroids, vertex colorings and nowhere-zero flows are dual concepts. In particular, if G is a plane graph and H its planar dual, then χ(G) = ξ(H). We shall see that a similar correspondence holds between the concepts of star chromatic number and star flow index.

3 Flows in Matroids

The proper setting for the study of flows and colorings is that of regular matroids. We assume familiarity with the circuit/cocircuit axioms of basic matroid theory such as in [13]. Let C (B) denote the {0,1}- valued circuit-element (cocircuit-element) incidence matrix of a matroid M. If M is binary then, over GF(2), we have CB^{⊤} = 0. An orientation ω(M) of M is a signing (1 ↦ ±1) of the elements of C and B such that CB^{⊤} = 0 as rational matrices. It is well known that a binary matroid is orientable if and only if it is regular. (See [13] for terminology and a proof.) It is a good exercise to find the relationship between orientations of a graph G and of the graphic matroid M(G). For any circuit C in ω(M), let C^{+} (C^{−}) denote the set of elements in C which are positively (negatively) oriented with respect to ω(M). For any cocircuit B in ω(M), we define B^{+} and B^{−} similarly.

Let Γ be an abelian group. A Γ-flow in a regular matroid M is an orientation ω(M) and a function f : M → Γ such that for every cocircuit B, ∑_{e∈B^{+}} f(e) = ∑_{e∈B^{−}} f(e). A flow f is said to be nowherezero if f(e) ≠ 0, for all e ∈ M. An integer flow is a Γ-flow where Γ = , the ring of integers. For integers 0 < d < k, a (k, d)-flow is an integer flow with values in the set {±d, ±(d + 1), …, ±(k − d)}, and a nowhere-zero k-flow is a (k, 1)-flow. As with graphs, the star flow index ξ^{∗}(M) is the infimum of k/d over all (k, d)-flows in M, and the flow index ξ(M) is the minimum k for which M has a nowhere-zero k-flow.

The following facts about nowhere-zero flows are well known and can be found in [11].

Proposition 3.1 Let ω(M) be an oriented regular matroid.

1. If M has no coloops (one-element cocircuits) then M has a nowhere-zero k-flow for some integer k, and hence ξ(M) and ξ^{∗}(M) are bounded.

2. For any abelian group Γ of order k, M has a nowhere-zero Γ-flow if and only if M has a nowherezero k-flow. Furthermore, if f is a Z_{k}-flow in M, then M has a k-flow f′ such that f′(e) ≡ f(e) (mod k), for all e ∈ E.

Our starting point is the following lemma, due to Hoffman [7].

Lemma 3.2 (Hoffman’s Lemma) Let M be an oriented regular matroid. Given a pair of non-negative rational functions l, u : M → such that 0 ≤ l(e) ≤ u(e) for e ∈ M, there exists a rational flow f : M → such that l(e) ≤ f(e) ≤ u(e) for every e ∈ M if and only if, for every cocircuit B,

∑_{e∈B^{+}} l(e) ≤ ∑_{e∈B^{−}} u(e) and ∑_{e∈B^{−}} l(e) ≤ ∑_{e∈B^{+}} u(e).  (1)

Additionally, f can be chosen to be integer valued provided that l and u are integer valued.

In case M is graphic, Hoffman’s Lemma is just the Ford-Fulkerson flow theorem [3]. If M is cographic then this is the Potential Differences Existence Theorem of Ghouila-Houri [5]. If l(e) ≡ l and u(e) ≡ u are constant, then (1) becomes:

\frac{l}{u} ≤ \frac{|B^{+}|}{|B^{−}|} ≤ \frac{u}{l}.

Thus by Hoffman’s Lemma with l ≡ d and u ≡ k − d, we obtain the following.

Theorem 3.3 A regular matroid M has a (k, d)-flow if and only if there exists some orientation ω(M) such that, for any cocircuit B, d/(k − d) ≤ |B^{+}|/|B^{−}| ≤ (k − d)/d.

Corollary 3.4 The star flow index ξ^{∗}(M) of a regular matroid M is the minimum over all orientations ω(M) of

1 + max\{\frac{|B^{+}|}{|B^{−}|}, \frac{|B^{−}|}{|B^{+}|} : B is a cocircuit in ω(M)\}.

= max\{\frac{|B|}{|B^{−}|}, \frac{|B|}{|B^{+}|} : B is a cocircuit in ω(M)\}.

This maximum is unbounded (and hence ξ^{∗}(M) := ∞) if and only if M has a coloop. Putting d = 1, we have that for any regular matroid M,

ξ(M) = ⌈ξ^{∗}(M)⌉.

A (k, d)-coloring c : V (G) → Z_{k} of an (arbitrarily oriented) graph G induces a Z_{k}-nowhere-zero flow f in the cographic matroid M^{∗}(G) by letting f(xy) = c(x) − c(y) for every arc xy ∈ G. By 2. of Proposition 3.1, this is equivalent to the existence of an integer flow in M^{∗}(G) whose values range in absolute value between d and k − d, that is, a (k, d)-flow in M^{∗}(G). This process can be reversed to obtain a (k, d)-coloring of G from a (k, d)-flow of M^{∗}(G). Thus from Theorem 3.3 we have the following.

Corollary 3.5 The star chromatic number χ^{∗}(G) = ξ^{∗}(M^{∗}(G)) of a graph G equals

min_{ω(G)} max_{C}\{\frac{|C|}{|C^{+}|}, \frac{|C|}{|C^{−}|}\}

where the minimum is over all orientations of G and the maximum is over all circuits of G.

We note that the characterization of the (integer) chromatic number χ = ⌈χ^{∗}⌉ of a graph via the formula of Corollary 3.5 was proved independently of Hoffman’s Lemma by Minty [9].

4 Some Observations Regarding χ^{∗} and ξ^{∗}

(1) Vince’s results [12] regarding the star-chromatic number of a graph immediately follow from Corollary 3.5. For example, in the case of the odd circuit C_{2k+1}, at least k + 1 edges must be similarly oriented in any orientation and hence χ^{∗}(C_{2k+1}) = (2k + 1)/k = 2 + 1/k.

(2) Let c : V → Z_{k} be a (k, d)-coloring of a graph G = (V, E). For each a ∈ Z_{k} let I(a) denote the independent set {v ∈ V : c(v) ∈ {a, a+1, …, a+d−1} (mod k) }. The k independent sets {I(a) : a ∈ Z_{k}} together cover every vertex exactly d times. Let us call such a collection a (k, d)-independent cover. Since any graph with a (k, d)-independent cover has an independent set of size at least |V |d/k, it follows that α(G) ≥ |V |/χ^{∗}(G), an improvement on the well-known bound |V |/χ(G).

Although a (k, d)-coloring always provides a (k, d)-independent cover, the two concepts are not equivalent. Take, for example, the graph G_{10} on 10 vertices and 35 edges obtained by adding all edges joining two disjoint circuits of length five. Each ‘side’ of G_{10} induces a C_{5} subgraph and hence has a (5, 2)- independent cover. Two such covers, one from each ‘side’, form a (10, 2)-independent cover of G_{10}. On the other hand, G_{10} does not admit a (10, 2)-coloring as χ(G_{10}) = 6.

(3) A weighted independent cover is a collection of independent sets, each of which is assigned a positive rational weight, such that the total weight of the sets containing each vertex is at least 1. The fractional chromatic number χ^{f}(G) is defined to be the least total weight of any weighted independent cover of G. This parameter has been studied in several papers (see [4],[6] for example). As the existence of a (k, d)-independent cover of G implies χ^{f}(G) ≤ k/d we have the following.

Observation 4.1 For any graph G, χ^{f}(G) ≤ χ^{∗}(G).

Equality does not always hold here; for instance, χ^{f}(G_{10}) = 5 while χ^{∗}(G_{10}) = 6. (We leave these for the reader to check!)

(4) Let the graph G = (V, E_{1}∪E_{2}) be the union two subgraphs G_{1} = (V, E_{1}) and G_{2} = (V, E_{2}). Obviously, χ(G) ≤ χ(G_{1})χ(G_{2}). Such a product formula also holds for the flow index — a fact utilized in Seymour’s proof [10] that ξ(G) ≤ 6 = 2 × 3 for any 2-edge connected graph G. Unfortunately analogous statements, where χ and ξ are replaced by χ^{∗} and ξ^{∗}, are false. A counterexample for χ^{∗} is provided again by the graph G_{10}; the star chromatic number of the disjoint union of two C_{5}’s is 2.5 and χ^{∗}(K_{5,5}) = 2, whereas χ^{∗}(G_{10}) = 6. Using a similar construction one can find, for any pair of rational numbers a, b ≥ 2, a graph G consisting of two subgraphs G_{1} and G_{2}, such that χ^{∗}(G_{1}) = a, χ^{∗}(G_{2}) = b and χ^{∗}(G) = ⌈a⌉⌈b⌉. Analogous examples exist for ξ^{∗}.

(5) We finish with an extension of the notion of chromatic number to (general) orientable matroids. As explained in [2], orientable matroids need not be binary (as is tacitly assumed in some works such as [13]). The following definition is more general than — but consistent with — that given in in Section 3. An orientation of an arbitrary matroid is a signing 1 → ±1 of C and B such that, for any row C of C and any row B of B, if C_{e}, B_{e} ≠ 0 for some e ∈ E, then there exists f ∈ E\{e} such that one of C_{e}B_{e}, C_{f}B_{f} equals +1 and the other equals −1. A matroid is orientable if it has at least one orientation. One can use Corollaries 3.4 and 3.5 to define ξ^{∗}(M) and χ^{∗}(M) (and hence ξ(M) and χ(M)) for an arbitrary orientable matroid M. There are several natural questions one might ask. For example, the chromatic number of a (loop-free) orientable matroid of rank r is bounded by the size of its largest circuit, which is at most r + 1. However, we do not know whether the flow index of a (coloop-free) orientable matroid of bounded rank is bounded. (This is true for regular matroids since their underlying simple matroids have bounded size.)

Two orientations of M are said to belong to the same reorientation class if one is obtained from the other by multiplying a corresponding set of columns of B and C by −1. Although regular matroids have only one reorientation class, orientable matroids can have many reorientation classes. Winfried Hochstättler has pointed out that it may be more sensible to define ξ^{∗} (and χ^{∗}) for each reorientation class ψ(M) of M by appropriately restricting the minimum in Corollary 3.4.

Definition 4.2 The star flow index of a reorientation class ψ(M) of an orientable matroid M is given by

ξ^{∗}(ψ(M)) = min_{ω∈ψ(M)} max_{B}\{\frac{|B|}{|B^{+}|}, \frac{|B|}{|B^{−}|}\}.

where the maximum is taken over the cocircuits B of M.

References

[1] J. A. Bondy and P. Hell, On the star chromatic number, J. Graph Theory 14 (1990) 479-482.

[2] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, G. M. Ziegler, Oriented Matroids, Encyclopedia of Mathematics and its Applications 46, Cambridge University Press, Cambridge (1993).

[3] L. R. Ford and D. R. Fulkerson, Maximal flow through a network, Canad. J. Math. 8 (1956) 399-404.

[4] Z. Füredi, Matching and covering in hypergraphs, Graphs and Combinatorics 4 (1988) 115-206.

[5] A. Ghouila-Houri, Sur l’existence d’un flot ou d’une tension prenant ses valeurs dans un groupe abélien, C. R. Acad. Sciences 250 (1960) 3931-3932.

[6] P. Hell and F. Roberts, Analogues of the Shannon capacity of a graph, Ann. Discrete Math. 12 (1982) 155-186.

[7] A. J. Hoffman, Some recent applications of the theory of linear inequalities to extremal combinatorial analysis, Combinatorial Analysis: Proceedings of the Tenth Symposium in Applied Mathematics of the American Mathematical Society, R. Bellman and M. Hall Jr. Eds., American Mathematical Society (1960) 113-128.

[8] F. Jaeger, Nowhere-zero flow problems, in Selected Topics in Graph Theory, Vol. 3, L. Beineke and R. Wilson Eds., Academic Press, New York (1988) 91-95.

[9] G. J. Minty, A theorem on n-coloring the points of a linear graph, Amer. Math. Monthly 69 (1962) 623-624.

[10] P. D. Seymour, Nowhere-zero 6-flows, J. Combin. Theory Ser. B 30 (1981) 130-135.

[11] W. T. Tutte, A contribution to the theory of chromatic polynomials. Canad. J. Math. 6 (1955) 80-91.

[12] A. Vince, Star chromatic number, J. Graph Theory 12 (1988) 551-559.

[13] D. Welsh, Matroid Theory, Academic Press, San Francisco (1976).

[14] X. Zhu, Star chromatic numbers and products of graphs, J. Graph Theory 16 (1992) 557-569.