Asymptotically optimal bound on the adjacent vertex distinguishing edge choice number

An adjacent vertex distinguishing edge coloring of a graph G without isolated edges is its proper edge coloring such that no pair of adjacent vertices meets the same set of colors in G. We show that such coloring can be chosen from any set of lists associated to the edges of G as long as the size of every list is at least , where Δ is the maximum degree of G and C is a constant. The proof is probabilistic. The same is true in the environment of total colorings.     

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.     

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 .     

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.     

On the Neighbor Sum Distinguishing Index of Planar Graphs

Let c be a proper edge coloring of a graph with integers . Then , while Vizing's theorem guarantees that we can take . On the course of investigating irregularities in graphs, it has been conjectured that with only slightly larger k, that is, , we could enforce an additional strong feature of c, namely that it attributes distinct sums of incident colors to adjacent vertices in G if only this graph has no isolated edges and is not isomorphic to C₅. We prove the conjecture is valid for planar graphs of sufficiently large maximum degree. In fact an even stronger statement holds, as the necessary number of colors stemming from the result of Vizing is proved to be sufficient for this family of graphs. Specifically, our main result states that every planar graph G of maximum degree at least 28, which contains no isolated edges admits a proper edge coloring such that for every edge of G.     

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.

相似文献   

Polychromatic colorings of complete graphs with respect to 1‐, 2‐factors and Hamiltonian cycles

If G is a graph and is a set of subgraphs of G, then an edge‐coloring of G is called ‐polychromatic if every graph from gets all colors present in G. The ‐polychromatic number of G, denoted , is the largest number of colors such that G has an ‐polychromatic coloring. In this article, is determined exactly when G is a complete graph and is the family of all 1‐factors. In addition is found up to an additive constant term when G is a complete graph and is the family of all 2‐factors, or the family of all Hamiltonian cycles.     

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.     

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.     

Strong Chromatic Index of Chordless Graphs

A strong edge coloring of a graph is an assignment of colors to the edges of the graph such that for every color, the set of edges that are given that color form an induced matching in the graph. The strong chromatic index of a graph G, denoted by , is the minimum number of colors needed in any strong edge coloring of G. A graph is said to be chordless if there is no cycle in the graph that has a chord. Faudree, Gyárfás, Schelp, and Tuza (The Strong Chromatic Index of Graphs, Ars Combin 29B (1990), 205–211) considered a particular subclass of chordless graphs, namely, the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan (Strong Chromatic Index of 2‐degenerate Graphs, J Graph Theory, 73(2) (2013), 119–126) answered this question in the affirmative by proving that if G is a chordless graph with maximum degree Δ, then . We improve this result by showing that for every chordless graph G with maximum degree Δ, . This bound is tight up to an additive constant.     

Minimal Obstructions for 1‐Immersions and Hardness of 1‐Planarity Testing

A graph is 1‐planar if it can be drawn on the plane so that each edge is crossed by no more than one other edge (and any pair of crossing edges cross only once). A non‐1‐planar graph G is minimal if the graph is 1‐planar for every edge e of G. We construct two infinite families of minimal non‐1‐planar graphs and show that for every integer , there are at least nonisomorphic minimal non‐1‐planar graphs of order n. It is also proved that testing 1‐planarity is NP‐complete.     

Solution of Vizing's Problem on Interchanges for the case of Graphs with Maximum Degree 4 and Related Results

Let G be a Class 1 graph with maximum degree 4 and let be an integer. We show that any proper t‐edge coloring of G can be transformed to any proper 4‐edge coloring of G using only transformations on 2‐colored subgraphs (so‐called interchanges). This settles the smallest previously unsolved case of a well‐known problem of Vizing on interchanges, posed in 1965. Using our result we give an affirmative answer to a question of Mohar for two classes of graphs: we show that all proper 5‐edge colorings of a Class 1 graph with maximum degree 4 are Kempe equivalent, that is, can be transformed to each other by interchanges, and that all proper 7‐edge colorings of a Class 2 graph with maximum degree 5 are Kempe equivalent.     

Extracting List Colorings from Large Independent Sets

We take an application of the Kernel Lemma by Kostochka and Yancey [11] to its logical conclusion. The consequence is a sort of magical way to draw conclusions about list coloring (and online list coloring) just from the existence of an independent set incident to many edges. We use this to prove an Ore‐degree version of Brooks' Theorem for online list‐coloring. The Ore‐degree of an edge in a graph G is . The Ore‐degree of G is . We show that every graph with and is online ‐choosable. In addition, we prove an upper bound for online list‐coloring triangle‐free graphs: . Finally, we characterize Gallai trees as the connected graphs G with no independent set incident to at least edges.     

Monochromatic Cycle Partitions in Local Edge Colorings

An edge coloring of a graph is said to be an r‐local coloring if the edges incident to any vertex are colored with at most r colors. Generalizing a result of Bessy and Thomassé, we prove that the vertex set of any 2‐locally colored complete graph may be partitioned into two disjoint monochromatic cycles of different colors. Moreover, for any natural number r, we show that the vertex set of any r‐locally colored complete graph may be partitioned into disjoint monochromatic cycles. This generalizes a result of Erd?s, Gyárfás, and Pyber.     

Some results on cyclic interval edge colorings of graphs

A proper edge coloring of a graph G with colors is called a cyclic interval t‐coloring if for each vertex v of G the edges incident to v are colored by consecutive colors, under the condition that color 1 is considered as consecutive to color t. We prove that a bipartite graph G of even maximum degree admits a cyclic interval ‐coloring if for every vertex v the degree satisfies either or . We also prove that every Eulerian bipartite graph G with maximum degree at most eight has a cyclic interval coloring. Some results are obtained for ‐biregular graphs, that is, bipartite graphs with the vertices in one part all having degree a and the vertices in the other part all having degree b; it has been conjectured that all these have cyclic interval colorings. We show that all (4, 7)‐biregular graphs as well as all ‐biregular () graphs have cyclic interval colorings. Finally, we prove that all complete multipartite graphs admit cyclic interval colorings; this proves a conjecture of Petrosyan and Mkhitaryan.     

Acyclic Chromatic Indices of Planar Graphs with Girth At Least 4

An acyclic edge coloring of a graph G is a proper edge coloring such that no bichromatic cycles are produced. The acyclic chromatic index of G is the smallest integer k such that G has an acyclic edge coloring using k colors. Fiamik (Math. Slovaca 28 (1978), 139–145) and later Alon et al. (J Graph Theory 37 (2001), 157–167) conjectured that for any simple graph G with maximum degree Δ. In this article, we confirm this conjecture for planar graphs of girth at least 4.     

On Perfect Matching Coverings and Even Subgraph Coverings

A perfect matching covering of a graph G is a set of perfect matchings of G such that every edge of G is contained in at least one member of it. Berge conjectured that every bridgeless cubic graph admits a perfect matching covering of order at most 5 (we call such a collection of perfect matchings a Berge covering of G). A cubic graph G is called a Kotzig graph if G has a 3‐edge‐coloring such that each pair of colors forms a hamiltonian circuit (introduced by R. Häggkvist, K. Markström, J Combin Theory Ser B 96 (2006), 183–206). In this article, we prove that if there is a vertex w of a cubic graph G such that , the graph obtained from by suppressing all degree two vertices is a Kotzig graph, then G has a Berge covering. We also obtain some results concerning the so‐called 5‐even subgraph double cover conjecture.     

Coloring Triple Systems with Local Conditions

We produce an edge‐coloring of the complete 3‐uniform hypergraph on n vertices with colors such that the edges spanned by every set of five vertices receive at least three distinct colors. This answers the first open case of a question of Conlon‐Fox‐Lee‐Sudakov (Int Math Res Not, to appear)  who asked whether such a coloring exists with colors.     

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.     

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.