Partitioning 2‐Edge‐Colored Ore‐Type Graphs by Monochromatic Cycles

Consider a graph G on n vertices satisfying the following Ore‐type condition: for any two nonadjacent vertices x and y of G, we have . We conjecture that if we color the edges of G with two colors then the vertex set of G can be partitioned to two vertex disjoint monochromatic cycles of distinct colors. In this article, we prove an asymptotic version of this conjecture.     

Splitting Planar Graphs of Girth 6 into Two Linear Forests with Short Paths

Recently, Borodin, Kostochka, and Yancey (Discrete Math 313(22) (2013), 2638–2649) showed that the vertices of each planar graph of girth at least 7 can be 2‐colored so that each color class induces a subgraph of a matching. We prove that any planar graph of girth at least 6 admits a vertex coloring in colors such that each monochromatic component is a path of length at most 14. Moreover, we show a list version of this result. On the other hand, for each positive integer , we construct a planar graph of girth 4 such that in any coloring of vertices in colors there is a monochromatic path of length at least t. It remains open whether each planar graph of girth 5 admits a 2‐coloring with no long monochromatic paths.     

An Improved Bound for Vertex Partitions by Connected Monochromatic K‐Regular Graphs

Improving a result of Sárközy and Selkow, we show that for all integers there exists a constant such that if and the edges of the complete graph are colored with r colors then the vertex set of can be partitioned into at most vertex disjoint connected monochromatic k‐regular subgraphs and vertices. This is close to best possible. © 2012 Wiley Periodicals, Inc. J. Graph Theory 73: 127–145, 2013     

Monochromatic Kr‐Decompositions of Graphs

Given graphs G and H, and a coloring of the edges of G with k colors, a monochromatic H‐decomposition of G is a partition of the edge set of G such that each part is either a single edge or forms a monochromatic graph isomorphic to H. Let be the smallest number ? such that any graph G of order n and any coloring of its edges with k colors, admits a monochromatic H‐decomposition with at most ? parts. Here, we study the function for and .     

Edge‐colorings avoiding rainbow stars

We consider an extremal problem motivated by a article of Balogh [J. Balogh, A remark on the number of edge colorings of graphs, European Journal of Combinatorics 27, 2006, 565–573], who considered edge‐colorings of graphs avoiding fixed subgraphs with a prescribed coloring. More precisely, given , we look for n‐vertex graphs that admit the maximum number of r‐edge‐colorings such that at most colors appear in edges incident with each vertex, that is, r‐edge‐colorings avoiding rainbow‐colored stars with t edges. For large n, we show that, with the exception of the case , the complete graph is always the unique extremal graph. We also consider generalizations of this problem.     

Approximations to m‐Colored Complete Infinite Hypergraphs

Given an edge coloring of a graph with a set of m colors, we say that the graph is exactly m‐colored if each of the colors is used. In 1999, Stacey and Weidl, partially resolving a conjecture of Erickson from 1994, showed that for a fixed natural number and for all sufficiently large k, there is a k‐coloring of the complete graph on such that no complete infinite subgraph is exactly m‐colored. In the light of this result, we consider the question of how close we can come to finding an exactly m‐colored complete infinite subgraph. We show that for a natural number m and any finite coloring of the edges of the complete graph on with m or more colors, there is an exactly ‐colored complete infinite subgraph for some satisfying ; this is best possible up to the additive constant. We also obtain analogous results for this problem in the setting of r‐uniform hypergraphs. Along the way, we also prove a recent conjecture of the second author and investigate generalizations of this conjecture to r‐uniform hypergraphs.     

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 .     

Large Subgraphs in Rainbow‐Triangle Free Colorings

Fox–Grinshpun–Pach showed that every 3‐coloring of the complete graph on n vertices without a rainbow triangle contains a clique of size that uses at most two colors, and this bound is tight up to the constant factor. We show that if instead of looking for large cliques one only tries to find subgraphs of large chromatic number, one can do much better. We show that every such coloring contains a 2‐colored subgraph with chromatic number at least , and this is best possible. We further show that for fixed positive integers with , every r‐coloring of the edges of the complete graph on n vertices without a rainbow triangle contains a subgraph that uses at most s colors and has chromatic number at least , and this is best possible. Fox–Grinshpun–Pach previously showed a clique version of this result. As a direct corollary of our result we obtain a generalization of the celebrated theorem of Erd?s‐Szekeres, which states that any sequence of n numbers contains a monotone subsequence of length at least . We prove that if an r‐coloring of the edges of an n‐vertex tournament does not contain a rainbow triangle then there is an s‐colored directed path on vertices, which is best possible. This gives a partial answer to a question of Loh.     

Interval Non‐edge‐Colorable Bipartite Graphs and Multigraphs

An edge‐coloring of a graph G with colors is called an interval t‐coloring if all colors are used, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1991, Erd?s constructed a bipartite graph with 27 vertices and maximum degree 13 that has no interval coloring. Erd?s's counterexample is the smallest (in a sense of maximum degree) known bipartite graph that is not interval colorable. On the other hand, in 1992, Hansen showed that all bipartite graphs with maximum degree at most 3 have an interval coloring. In this article, we give some methods for constructing of interval non‐edge‐colorable bipartite graphs. In particular, by these methods, we construct three bipartite graphs that have no interval coloring, contain 20, 19, 21 vertices and have maximum degree 11, 12, 13, respectively. This partially answers a question that arose in [T.R. Jensen, B. Toft, Graph coloring problems, Wiley Interscience Series in Discrete Mathematics and Optimization, 1995, p. 204]. We also consider similar problems for bipartite multigraphs.     

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 .     

Facial Nonrepetitive Vertex Coloring of Plane Graphs

A sequence is a repetition. A sequence S is nonrepetitive, if no subsequence of consecutive terms of S is a repetition. Let G be a plane graph. That is, a planar graph with a fixed embedding in the plane. A facial path consists of consecutive vertices on the boundary of a face. A facial nonrepetitive vertex coloring of a plane graph G is a vertex coloring such that the colors assigned to the vertices of any facial path form a nonrepetitive sequence. Let denote the minimum number of colors of a facial nonrepetitive vertex coloring of G. Harant and Jendrol’ conjectured that can be bounded from above by a constant. We prove that for any plane graph G.     

Parity Linkage and the Erdős–Pósa Property of Odd Cycles through Prescribed Vertices in Highly Connected Graphs

We show the following for every sufficiently connected graph G , any vertex subset S of G , and given integer k : there are k disjoint odd cycles in G each containing a vertex of S or there is set X of at most vertices such that does not contain any odd cycle that contains a vertex of S . We prove this via an extension of Kawarabayashi and Reed's result about parity‐k‐linked graphs (Combinatorica 29, 215–225). From this result, it is easy to deduce several other well‐known results about the Erd?s–Pósa property of odd cycles in highly connected graphs. This strengthens results due to Thomassen (Combinatorica 21, 321–333), and Rautenbach and Reed (Combinatorica 21, 267–278), respectively.     

Improved Upper Bounds for Gallai–Ramsey Numbers of Paths and Cycles

Given a graph G and a positive integer k, define the Gallai–Ramsey number to be the minimum number of vertices n such that any k‐edge coloring of contains either a rainbow (all different colored) triangle or a monochromatic copy of G. In this work, we improve upon known upper bounds on the Gallai–Ramsey numbers for paths and cycles. All these upper bounds now have the best possible order of magnitude as functions of k.     

Extremal graphs for the k‐flower

The Turán number of a graph H, , is the maximum number of edges in any graph of order n that does not contain an H as a subgraph. A graph on vertices consisting of k triangles that intersect in exactly one common vertex is called a k‐fan, and a graph consisting of k cycles that intersect in exactly one common vertex is called a k‐flower. In this article, we determine the Turán number of any k‐flower containing at least one odd cycle and characterize all extremal graphs provided n is sufficiently large. Erdős, Füredi, Gould, and Gunderson determined the Turán number for the k‐fan. Our result is a generalization of their result. The addition aim of this article is to draw attention to a powerful tool, the so‐called progressive induction lemma of Simonovits.     

Characterizing Graphs with Crossing Number at Least 2

Our main result includes the following, slightly surprising, fact: a 4‐connected nonplanar graph G has crossing number at least 2 if and only if, for every pair of edges having no common incident vertex, there are vertex‐disjoint cycles in G with one containing e and the other containing f.     

Acyclic List Edge Coloring of Graphs

A proper edge coloring of a graph is said to be acyclic if any cycle is colored with at least three colors. An edge-list L of a graph G is a mapping that assigns a finite set of positive integers to each edge of G. An acyclic edge coloring ? of G such that for any is called an acyclic L-edge coloring of G. A graph G is said to be acyclically k-edge choosable if it has an acyclic L‐edge coloring for any edge‐list L that satisfies for each edge e. The acyclic list chromatic index is the least integer k such that G is acyclically k‐edge choosable. We develop techniques to obtain bounds for the acyclic list chromatic indices of outerplanar graphs, subcubic graphs, and subdivisions of Halin graphs.     

Long cycles through prescribed vertices have the Erdős‐Pósa property

We prove that for every graph, any vertex subset S, and given integers : there are k disjoint cycles of length at least ℓ that each contain at least one vertex from S, or a vertex set of size that meets all such cycles. This generalizes previous results of Fiorini and Herinckx and of Pontecorvi and Wollan. In addition, we describe an algorithm for our main result that runs in time, where s denotes the cardinality of S.     

On Neighbor‐Distinguishing Index of Planar Graphs

A proper edge coloring of a graph G without isolated edges is neighbor‐distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The neighbor‐distinguishing index of G is the minimum number ndi(G) of colors in a neighbor‐distinguishing edge coloring of G. Zhang, Liu, and Wang in 2002 conjectured that if G is a connected graph of order at least 6. In this article, the conjecture is verified for planar graphs with maximum degree at least 12.     

On Choosability with Separation of Planar Graphs with Forbidden Cycles

We study choosability with separation which is a constrained version of list coloring of graphs. A ‐list assignment L of a graph G is a function that assigns to each vertex v a list of at least k colors and for any adjacent pair , the lists and share at most d colors. A graph G is ‐choosable if there exists an L‐coloring of G for every ‐list assignment L. This concept is also known as choosability with separation. We prove that planar graphs without 4‐cycles are (3, 1)‐choosable and that planar graphs without 5‐ and 6‐cycles are (3, 1)‐choosable. In addition, we give an alternative and slightly stronger proof that triangle‐free planar graphs are (3, 1)‐choosable.     

Coloring Cubic Graphs by Point‐Intransitive Steiner Triple Systems

An ‐coloring of a cubic graph G is an edge coloring of G by points of a Steiner triple system such that the colors of any three edges meeting at a vertex form a block of . A Steiner triple system that colors every simple cubic graph is said to be universal. It is known that every nontrivial point‐transitive Steiner triple system that is neither projective nor affine is universal. In this article, we present the following results.

相似文献