Antimagic Labeling of Regular Graphs

A graph is antimagic if there is a one‐to‐one correspondence such that for any two vertices , . It is known that bipartite regular graphs are antimagic and nonbipartite regular graphs of odd degree at least three are antimagic. Whether all nonbipartite regular graphs of even degree are antimagic remained an open problem. In this article, we solve this problem and prove that all even degree regular graphs are antimagic.     

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 .     

Large Monochromatic Triple Stars in Edge Colourings

Following problems posed by Gyárfás 2011, we show that for every r‐edge‐colouring of there is a monochromatic triple star of order at least , improving Ruszinkó's result 2012. An edge colouring of a graph is called a local r‐colouring if every vertex spans edges of at most r distinct colours. We prove the existence of a monochromatic triple star with at least vertices in every local r‐colouring of .     

Saturation numbers for families of graph subdivisions

For a family of graphs, a graph G is ‐saturated if G contains no member of as a subgraph, but for any edge in , contains some member of as a subgraph. The minimum number of edges in an ‐saturated graph of order n is denoted . A subdivision of a graph H, or an H‐subdivision, is a graph G obtained from H by replacing the edges of H with internally disjoint paths of arbitrary length. We let denote the family of H‐subdivisions, including H itself. In this paper, we study when H is one of or , obtaining several exact results and bounds. In particular, we determine exactly for and show for n sufficiently large that there exists a constant such that . For we show that will suffice, and that this can be improved slightly depending on the value of . We also give an upper bound on for all t and show that . This provides an interesting contrast to a 1937 result of Wagner (Math Ann, 114 (1937), 570–590), who showed that edge‐maximal graphs without a K₅‐minor have at least edges.     

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.     

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 .     

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 , .     

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.     

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.     

Destroying Noncomplete Regular Components in Graph Partitions

We prove that if G is a graph and such that then can be partitioned into sets such that and contains no noncomplete ‐regular components for each . In particular, the vertex set of any graph G can be partitioned into sets, each of which induces a disjoint union of triangles and paths.     

Toughness and Vertex Degrees

We study theorems giving sufficient conditions on the vertex degrees of a graph G to guarantee G is t‐tough. We first give a best monotone theorem when , but then show that for any integer , a best monotone theorem for requires at least nonredundant conditions, where grows superpolynomially as . When , we give an additional, simple theorem for G to be t‐tough, in terms of its vertex degrees.     

Antimagic Labeling of Cubic Graphs

An antimagic labeling of a graph G is a one‐to‐one correspondence between and such that the sum of the labels assigned to edges incident to distinct vertices are different. If G has an antimagic labeling, then we say G is antimagic. This article proves that cubic graphs are antimagic.     

Average Degree in Graph Powers

The kth power of a simple graph G, denoted by , is the graph with vertex set where two vertices are adjacent if they are within distance k in G. We are interested in finding lower bounds on the average degree of . Here we prove that if G is connected with minimum degree and , then G⁴ has average degree at least . We also prove that if G is a connected d‐regular graph on n vertices with diameter at least , then the average degree of is at least Both these results are shown to be essentially best possible; the second is best possible even when is arbitrarily large.     

Limits of Near‐Coloring of Sparse Graphs

Let be nonnegative integers. A graph G is ‐colorable if its vertex set can be partitioned into sets such that the graph induced by has maximum degree at most d for , while the graph induced by is an edgeless graph for . In this article, we give two real‐valued functions and such that any graph with maximum average degree at most is ‐colorable, and there exist non‐‐colorable graphs with average degree at most . Both these functions converge (from below) to when d tends to infinity. This implies that allowing a color to be d‐improper (i.e., of type ) even for a large degree d increases the maximum average degree that guarantees the existence of a valid coloring only by 1. Using a color of type (even with a very large degree d) is somehow less powerful than using two colors of type (two stable sets).     

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.     

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.     

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 .     

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.