Improper Coloring of Sparse Graphs with a Given Girth,II: Constructions

A graph G is ‐colorable if can be partitioned into two sets and so that the maximum degree of is at most j and of is at most k. While the problem of verifying whether a graph is (0, 0)‐colorable is easy, the similar problem with in place of (0, 0) is NP‐complete for all nonnegative j and k with . Let denote the supremum of all x such that for some constant every graph G with girth g and for every is ‐colorable. It was proved recently that . In a companion paper, we find the exact value . In this article, we show that increasing g from 5 further on does not increase much. Our constructions show that for every g, . We also find exact values of for all g and all .     

Circular Chromatic Indices of Regular Graphs

The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are adjacent. It is known that for any , there is a 3‐regular simple graph G with . This article proves the following results: Assume is an odd integer. For any , there is an n‐regular simple graph G with . For any , there is an n‐regular multigraph G with .     

Anti‐Ramsey Problems for t Edge‐Disjoint Rainbow Spanning Subgraphs: Cycles,Matchings, or Trees

We seek the maximum number of colors in an edge‐coloring of the complete graph not having t edge‐disjoint rainbow spanning subgraphs of specified types. Let , , and denote the answers when the spanning subgraphs are cycles, matchings, or trees, respectively. We prove for and for . We prove for and for . We also provide constructions for the more general problem in which colorings are restricted so that colors do not appear on more than q edges at a vertex.     

On Rooted Packings,Decompositions, and Factors of Graphs

In this article, we study so‐called rooted packings of rooted graphs. This concept is a mutual generalization of the concepts of a vertex packing and an edge packing of a graph. A rooted graph is a pair , where G is a graph and . Two rooted graphs and are isomorphic if there is an isomorphism of the graphs G and H such that S is the image of T in this isomorphism. A rooted graph is a rooted subgraph of a rooted graph if H is a subgraph of G and . By a rooted ‐packing into a rooted graph we mean a collection of rooted subgraphs of isomorphic to such that the sets of edges are pairwise disjoint and the sets are pairwise disjoint. In this article, we concentrate on studying maximum ‐packings when H is a star. We give a complete classification with respect to the computational complexity status of the problems of finding a maximum ‐packing of a rooted graph when H is a star. The most interesting polynomial case is the case when H is the 2‐edge star and S contains the center of the star only. We prove a min–max theorem for ‐packings in this case.     

k‐Kings in k‐Quasitransitive Digraphs

Let D be a digraph with vertex set and arc set . A vertex x is a k‐king of D, if for every , there is an ‐path of length at most k. A subset N of is k‐independent if for every pair of vertices , we have and ; it is l‐absorbent if for every there exists such that . A ‐kernel of D is a k‐independent and l‐absorbent subset of . A k‐kernel is a ‐kernel. A digraph D is k‐quasitransitive, if for any path of length k, x₀ and are adjacent. In this article, we will prove that a k‐quasitransitive digraph with has a k‐king if and only if it has a unique initial strong component and the unique initial strong component is not isomorphic to an extended ‐cycle where each has at least two vertices. Using this fact, we show that every strong k‐quasitransitive digraph has a ‐kernel.     

A Combined Logarithmic Bound on the Chromatic Index of Multigraphs

For a multigraph G, the integer round‐up of the fractional chromatic index provides a good general lower bound for the chromatic index . For an upper bound, Kahn 1996 showed that for any real there exists a positive integer N so that whenever . We show that for any multigraph G with order n and at least one edge, ). This gives the following natural generalization of Kahn's result: for any positive reals , there exists a positive integer N so that + c whenever . We also compare the upper bound found here to other leading upper bounds.     

Extremal Graphs With a Given Number of Perfect Matchings

Let denote the maximum number of edges in a graph having n vertices and exactly p perfect matchings. For fixed p, Dudek and Schmitt showed that for some constant when n is at least some constant . For , they also determined and . For fixed p, we show that the extremal graphs for all n are determined by those with vertices. As a corollary, a computer search determines and for . We also present lower bounds on proving that for (as conjectured by Dudek and Schmitt), and we conjecture an upper bound on . Our structural results are based on Lovász's Cathedral Theorem.     

Minors in ‐ Chromatic Graphs,II

Let denote the graph obtained from the complete graph by deleting the edges of some ‐subgraph. The author proved earlier that for each fixed s and , every graph with chromatic number has a minor. This confirmed a partial case of the corresponding conjecture by Woodall and Seymour. In this paper, we show that the statement holds already for much smaller t, namely, for .     

Partial Online List Coloring of Graphs

For a graph G, let be the maximum number of vertices of G that can be colored whenever each vertex of G is given t permissible colors. Albertson, Grossman, and Haas conjectured that if G is s‐choosable and , then . In this article, we consider the online version of this conjecture. Let be the maximum number of vertices of G that can be colored online whenever each vertex of G is given t permissible colors online. An analog of the above conjecture is the following: if G is online s‐choosable and then . This article generalizes some results concerning partial list coloring to online partial list coloring. We prove that for any positive integers , . As a consequence, if s is a multiple of t, then . We also prove that if G is online s‐choosable and , then and for any , .     

Finding for a Surface Σ of Characteristic −4

For each surface Σ, we define max G is a class two graph of maximum degree that can be embedded in . Hence, Vizing's Planar Graph Conjecture can be restated as if Σ is a sphere. In this article, by applying some newly obtained adjacency lemmas, we show that if Σ is a surface of characteristic . Until now, all known satisfy . This is the first case where .     

Transversals in Trees

The total embedding polynomial of a graph G is the bivariate polynomial where is the number of embeddings, for into the orientable surface , and is the number of embeddings, for into the nonorientable surface . The sequence is called the total embedding distribution of the graph G; it is known for relatively few classes of graphs, compared to the genus distribution . The circular ladder graph is the Cartesian product of the complete graph on two vertices and the cycle graph on n vertices. In this article, we derive a closed formula for the total embedding distribution of circular ladders.     

Biembedding a Steiner Triple System With a Hamilton Cycle Decomposition of a Complete Graph

We construct a face two‐colourable, blue and green say, embedding of the complete graph in a nonorientable surface in which there are blue faces each of which have a hamilton cycle as their facial walk and green faces each of which have a triangle as their facial walk; equivalently a biembedding of a Steiner triple system of order n with a hamilton cycle decomposition of , for all and . Using a variant of this construction, we establish the minimum genus of nonorientable embeddings of the graph , for where and .     

Decomposition of Sparse Graphs into Forests and a Graph with Bounded Degree

For a loopless multigraph G, the fractional arboricity Arb(G) is the maximum of over all subgraphs H with at least two vertices. Generalizing the Nash‐Williams Arboricity Theorem, the Nine Dragon Tree Conjecture asserts that if , then G decomposes into forests with one having maximum degree at most d. The conjecture was previously proved for ; we prove it for and when and . For , we can further restrict one forest to have at most two edges in each component. For general , we prove weaker conclusions. If , then implies that G decomposes into k forests plus a multigraph (not necessarily a forest) with maximum degree at most d. If , then implies that G decomposes into forests, one having maximum degree at most d. Our results generalize earlier results about decomposition of sparse planar graphs.     

The Set of Circular Flow Numbers of Regular Graphs

This article determines the set of the circular flow numbers of regular graphs. Let be the set of the circular flow numbers of graphs, and be the set of the circular flow numbers of d‐regular graphs. If d is even, then . For it is known 6 that . We show that . Hence, the interval is the only gap for circular flow numbers of ‐regular graphs between and 5. Furthermore, if Tutte's 5‐flow conjecture is false, then it follows, that gaps for circular flow numbers of graphs in the interval [5, 6] are due for all graphs not just for regular graphs.     

Structure Theorem for U5‐free Tournaments

Let U₅ be the tournament with vertices v₁, …, v₅ such that , and if , and . In this article, we describe the tournaments that do not have U₅ as a subtournament. Specifically, we show that if a tournament G is “prime”—that is, if there is no subset , , such that for all , either for all or for all —then G is U₅‐free if and only if either G is a specific tournament or can be partitioned into sets X, Y, Z such that , , and are transitive. From the prime U₅‐free tournaments we can construct all the U₅‐free tournaments. We use the theorem to show that every U₅‐free tournament with n vertices has a transitive subtournament with at least vertices, and that this bound is tight.     

Orientable Hamilton Cycle Embeddings of Complete Tripartite Graphs II: Voltage Graph Constructions and Applications

In an earlier article the authors constructed a hamilton cycle embedding of in a nonorientable surface for all and then used these embeddings to determine the genus of some large families of graphs. In this two‐part series, we extend those results to orientable surfaces for all . In part II, a voltage graph construction is presented for building embeddings of the complete tripartite graph on an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all such that p is prime, completing the proof started by part I (which covers the case ) that there exists an orientable hamilton cycle embedding of for all , . These embeddings are then used to determine the genus of several families of graphs, notably for and, in some cases, for .     

Eigenvalues of ‐Free Graphs and the Connectivity of Their Independence Complexes

Let G be a graph on n vertices, with maximal degree d, and not containing as an induced subgraph. We prove:

• 1.
• 2.

Here is the maximal eigenvalue of the Laplacian of G, is the independence complex of G, and denotes the topological connectivity of a complex plus 2. These results provide improved bounds for the existence of independent transversals in ‐free graphs.     

List Colorings with Distinct List Sizes,the Case of Complete Bipartite Graphs

Let be a function on the vertex set of the graph . The graph G is f‐choosable if for every collection of lists with list sizes specified by f there is a proper coloring using colors from the lists. The sum choice number, , is the minimum of , over all functions f such that G is f‐choosable. It is known (Alon, Surveys in Combinatorics, 1993 (Keele), London Mathematical Society Lecture Note Series, Vol. 187, Cambridge University Press, Cambridge, 1993, pp. 1–33, Random Struct Algor 16 (2000), 364–368) that if G has average degree d, then the usual choice number is at least , so they grow simultaneously. In this article, we show that can be bounded while the minimum degree . Our main tool is to give tight estimates for the sum choice number of the unbalanced complete bipartite graph .