Edge-coloring of multigraphs

We introduce a monotone invariant π(G) on graphs and show that it is an upper bound of the chromatic index of graphs. Moreover, there exist polynomial time algorithms for computing π(G) and for coloring edges of a multigraph G by π(G) colors. This generalizes the classical edge-coloring theorems of Shannon and Vizing.     

Complexity of 3-edge-coloring in the class of cubic graphs with a polyhedral embedding in an orientable surface

A polyhedral embedding in a surface is one in which any two faces have boundaries that are either disjoint or simply connected. In a cubic (3-regular) graph this is equivalent to the dual being a simple graph. In 1968, Grünbaum conjectured that every cubic graph with a polyhedral embedding in an orientable surface is 3-edge-colorable. For the sphere, this is equivalent to the Four-Color Theorem, but we have disproved the conjecture in the general form. In this paper we extend this result and show that if we restrict our attention to a class of cubic graphs with a polyhedral embedding in an orientable surface, then the computational complexity of the 3-edge-coloring problem and its approximation does not improve.     

A Theorem About Elementary Cuts and Flow Polynomials

It is known that the functions F_G(k) and I_G(k) evaluating the numbers of nowhere-zero _k- and k-flows in a graph G, respectively, are polynomials of k. If X is a totally cyclic orientation of G, then the number of integral flows having values 1,,k–1 on the arcs of X can be evaluated by a polynomial I_X(k). F_G(k) and I_G(k) can be expressed as sums of I_X(k). In this paper we show that the value I_X(k) is positive for every totally cyclic orientation X of G if and only if k is greater than or equal to the maximum cardinality of an elementary edge-cut of G.Acknowledgments.This paper was finished during visiting School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia.Mathematics Subject Classification (1991): 05C15, 05C20     

Restrictions On Smallest Counterexamples To The 5-Flow Conjecture

Using counting arguments, we show that every smallest counterexample to Tutte’s 5-flow Conjecture (that every bridgeless graph has a nowhere-zero 5-flow) has girth at least 9. * This work was supported by Science and Technology Assistance Agency under the contract No. APVT-51-027604 and partially by VEGA grant 2/4004/04. The author was also affiliated at the School of Mathematics, Georgia Institute of Technology, the Department of Mathematics, Vanderbilt University.     

Three measures of edge-uncolorability

We study three invariants of graphs measuring how far a graph is from having a proper 3-edge-coloring. We show that they have the same value on certain classes of graphs, in particular on the class of cubic graphs.     

Counting nowhere-zero flows on wheels

A wheel is a graph consisting from a vertex w and a circuit C such that each vertex of C is a neighbor of w. Two nowhere-zero group valued flows on a wheel are equivalent if their values differ only on the edges of C. We introduce recursive formulas for the numbers of classes of the same cardinality of this equivalence.     

A note on the arboricity of graphs

The well known theorem of Nash-Williams determines the graphs that are union ofk edge disjoint forests. The main result presented in this note is that any graph which is the union ofk edge disjoint forests is in fact a union ofk such forests in which if a vertex has degree at least 3 in one of the forests then its degree is positive in all the other forests. We also discuss consequences of this result with respect to the arboricity of regular graphs.     

Tension polynomials of graphs

The tension polynomial F_G(k) of a graph G, evaluating the number of nowhere‐zero ?_k‐tensions in G, is the nontrivial divisor of the chromatic polynomial χ_G(k) of G, in that χ_G(k) = k^c(G)F_G(k), where c(G) denotes the number of components of G. We introduce the integral tension polynomial I_G(k), which evaluates the number of nowhere‐zero integral tensions in G with absolute values smaller than k. We show that 2^r(G)F_G(k)≥I_G(k)≥ (r(G)+1)F_G(k), where r(G)=|V(G)|?c(G), and, for every k>1, F_G(k+1)≥ F_G(k)˙k / (k?1) and I_G(k+1)≥I_G(k)˙k/(k?1). © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 137–146, 2002     

A note on approximation of a ball by polytopes

We study properties of polytopes circumscribed by a unit sphere in Rⁿ with either m extreme points or m facets. We show that if one measures the quality of approximation using the radius of an inscribing sphere then asymptotically the best-possible results are the same for both cases. Somewhat surprisingly, however, the volume can grow substantially faster in m for the case where the polytope has m facets.