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.     

Spanning Trees with Vertices Having Large Degrees

Let G be a connected simple graph, and let f be a mapping from to the set of integers. This paper is concerned with the existence of a spanning tree in which each vertex v has degree at least . We show that if for any nonempty subset , then a connected graph G has a spanning tree such that for all , where is the set of neighbors v of vertices in S with , , and is the degree of x in T. This is an improvement of several results, and the condition is best possible.     

Cycles Avoiding a Color in Colorful Graphs

The Ramsey numbers of cycles imply that every 2‐edge‐colored complete graph on n vertices contains monochromatic cycles of all lengths between 4 and at least . We generalize this result to colors by showing that every k‐edge‐colored complete graph on vertices contains ‐edge‐colored cycles of all lengths between 3 and at least .     

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 .     

Total Vertex Irregularity Strength of Dense Graphs

Consider a graph of minimum degree δ and order n. Its total vertex irregularity strength is the smallest integer k for which one can find a weighting such that for every pair of vertices of G. We prove that the total vertex irregularity strength of graphs with is bounded from above by . One of the cornerstones of the proof is a random ordering of the vertices generated by order statistics.     

Equimatchable Graphs on Surfaces

A graph G is equimatchable if each matching in G is a subset of a maximum‐size matching and it is factor critical if has a perfect matching for each vertex v of G. It is known that any 2‐connected equimatchable graph is either bipartite or factor critical. We prove that for 2‐connected factor‐critical equimatchable graph G the graph is either or for some n for any vertex v of G and any minimal matching M such that is a component of . We use this result to improve the upper bounds on the maximum number of vertices of 2‐connected equimatchable factor‐critical graphs embeddable in the orientable surface of genus g to if and to if . Moreover, for any nonnegative integer g we construct a 2‐connected equimatchable factor‐critical graph with genus g and more than vertices, which establishes that the maximum size of such graphs is . Similar bounds are obtained also for nonorientable surfaces. In the bipartite case for any nonnegative integers g, h, and k we provide a construction of arbitrarily large 2‐connected equimatchable bipartite graphs with orientable genus g, respectively nonorientable genus h, and a genus embedding with face‐width k. Finally, we prove that any d‐degenerate 2‐connected equimatchable factor‐critical graph has at most vertices, where a graph is d‐degenerate if every its induced subgraph contains a vertex of degree at most d.     

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 .     

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 .     

Minimum Vertex Degree Threshold for ‐tiling*

We prove that the vertex degree threshold for tiling (the 3‐uniform hypergraph with four vertices and two triples) in a 3‐uniform hypergraph on vertices is , where if and otherwise. This result is best possible, and is one of the first results on vertex degree conditions for hypergraph tiling.     

On the Circular Chromatic Number of Graph Powers

This article intends to study some functors from the category of graphs to itself such that, for any graph G, the circular chromatic number of is determined by that of G. In this regard, we investigate some coloring properties of graph powers. We show that provided that . As a consequence, we show that if , then . In particular, and has no subgraph with circular chromatic number equal to . This provides a negative answer to a question asked in (X. Zhu, Discrete Math, 229(1–3) (2001), 371–410). Moreover, we investigate the nth multichromatic number of subdivision graphs. Also, we present an upper bound for the fractional chromatic number of subdivision graphs. Precisely, we show that .     

Neighbor Distinguishing Edge Colorings Via the Combinatorial Nullstellensatz Revisited

Consider a simple graph and its proper edge coloring c with the elements of the set . We say that c is neighbor set distinguishing (or adjacent strong) if for every edge , the set of colors incident with u is distinct from the set of colors incident with v. Let us then consider a stronger requirement and suppose we wish to distinguishing adjacent vertices by sums of their incident colors. In both problems the challenging conjectures presume that such colorings exist for any graph G containing no isolated edges if only . We prove that in both problems is sufficient. The proof is based on the Combinatorial Nullstellensatz, applied in the “sum environment.” In fact the identical bound also holds if we use any set of k real numbers instead of as edge colors, and the same is true in list versions of the both concepts. In particular, we therefore obtain that lists of length ( in fact) are sufficient for planar graphs.     

On 5‐Cycles and 6‐Cycles in Regular n‐Tournaments

Let T be a tournament of order n and be the number of cycles of length m in T. For and odd n, the maximum of is achieved for any regular tournament of order n (M. G. Kendall and B. Babington Smith, 1940), and in the case it is attained only for the unique regular locally transitive tournament RLT_n of order n (U. Colombo, 1964). A lower bound was also obtained for in the class of regular tournaments of order n (A. Kotzig, 1968). This bound is attained if and only if T is doubly regular (when ) or nearly doubly regular (when ) (B. Alspach and C. Tabib, 1982). In the present article, we show that for any regular tournament T of order n, the equality holds. This allows us to reduce the case to the case In turn, the pure spectral expression for obtained in the class implies that for a regular tournament T of order the inequality holds, with equality if and only if T is doubly regular or T is the unique regular tournament of order 7 that is neither doubly regular nor locally transitive. We also determine the value of c₆(RLT_n) and conjecture that this value coincides with the minimum number of 6‐cycles in the class for each odd      

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 Note on the Order of Iterated Line Digraphs

Given a digraph G, we propose a new method to find the recurrence equation for the number of vertices of the k‐iterated line digraph , for , where . We obtain this result by using the minimal polynomial of a quotient digraph of G.     

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 .     

Interval Minors of Complete Bipartite Graphs

Interval minors of bipartite graphs were recently introduced by Jacob Fox in the study of Stanley–Wilf limits. We investigate the maximum number of edges in ‐interval minor‐free bipartite graphs. We determine exact values when and describe the extremal graphs. For , lower and upper bounds are given and the structure of ‐interval minor‐free graphs is studied.     

Counterexamples to the List Square Coloring Conjecture

The square G² of a graph G is the graph defined on such that two vertices u and v are adjacent in G² if the distance between u and v in G is at most 2. Let and be the chromatic number and the list chromatic number of a graph H, respectively. A graph H is called chromatic‐choosable if . It is an interesting problem to find graphs that are chromatic‐choosable. Kostochka and Woodall (Choosability conjectures and multicircuits, Discrete Math., 240 (2001), 123–143) conjectured that for every graph G, which is called List Square Coloring Conjecture. In this article, we give infinitely many counter examples to the conjecture. Moreover, we show that the value can be arbitrarily large.     

On 2‐Colorings of Hypergraphs

In this article, we continue the study of 2‐colorings in hypergraphs. A hypergraph is 2‐colorable if there is a 2‐coloring of the vertices with no monochromatic hyperedge. Let denote the class of all k‐uniform k‐regular hypergraphs. It is known (see Alon and Bregman [Graphs Combin. 4 (1988) 303–306] and Thomassen [J. Amer. Math. Soc. 5 (1992), 217–229] that every hypergraph is 2‐colorable, provided . As remarked by Alon and Bregman the result is not true when , as may be seen by considering the Fano plane. Indeed there are several constructions for building infinite families of hypergraphs in that are not 2‐colorable. Our main result in this paper is a strengthening of the above results. For this purpose, we define a set X of vertices in a hypergraph H to be a free set in H if we can 2‐color such that every edge in H receives at least one vertex of each color. We conjecture that for , every hypergraph has a free set of size in H. We show that the bound cannot be improved for any and we prove our conjecture when . Our proofs use results from areas such as transversal in hypergraphs, cycles in digraphs, and probabilistic arguments.     

On the Edit Distance from ‐Free Graphs

The edit distance between two graphs on the same vertex set is defined to be the size of the symmetric difference of their edge sets. The edit distance function of a hereditary property, , is a function of p, and measures, asymptotically, the furthest graph of edge density p from under this metric. In this article, we address the hereditary property , the property of having no induced copy of the complete bipartite graph with two vertices in one class and t in the other. Employing an assortment of techniques and colored regularity graph constructions, we are able to determine the edit distance function over the entire domain when and extend the interval over which the edit distance function for is known for all values of t, determining its maximum value for all odd t. We also prove that the function for odd t has a nontrivial interval on which it achieves its maximum. These are the only known principal hereditary properties for which this occurs. In the process of studying this class of functions, we encounter some surprising connections to extremal graph theory problems, such as strongly regular graphs and the problem of Zarankiewicz.