Interval coloring of (3,4)‐biregular bipartite graphs having large cubic subgraphs

An interval coloring of a graph is a proper edge coloring such that the set of used colors at every vertex is an interval of integers. Generally, it is an NP‐hard problem to decide whether a graph has an interval coloring or not. A bipartite graph G = (A,B;E) is (α, β)‐biregular if each vertex in A has degree α and each vertex in B has degree β. In this paper we prove that if the (3,4)‐biregular graph G has a cubic subgraph covering the set B then G has an interval coloring. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 122–128, 2004     

On a cardinal group invariant related to decompositions of Abelian groups

For each Abelian groupG, a cardinal invariant χ(G) is introduced and its properties are studied. In the special caseG = ℤ ⁿ , the cardinalχ(ℤ ⁿ ) is equal to the minimal cardinality of an essential subset of ℤ ⁿ , i.e., a of a subsetA ⊂ ℤ ⁿ such that, for any coloring of the group ℤ ⁿ inn colors, there exists an infinite one-color subset that is symmetric with respect to some pointα ofA. The estimaten( ^{n +} l)/2 ≤χ(ℤ ⁿ ) < 2n is proved for alln and the relationχ(ℤ ⁿ ) =n(n + 1)/2 forn ≤ 3. The structure of essential subsets of cardinalityχ(ℤ ⁿ ) in ℤ ⁿ is completely described forn ≤ 3. Translated fromMatematicheskie Zametki, Vol. 64, No. 3, pp. 341–350, September, 1998.     

Variations on the Roy-Gallai theorem

A generalization of the Roy-Gallai Theorem on the chromatic number of a graph is derived which is also an extension of several other results of Berge and of Li. A simple inductive proof is given which provides a direct way of deriving the Theorem of Li. We also show that some classical results valid for optimal colorings cannot be transposed to suboptimal colorings. We finally investigate some elementary properties which are also valid in suboptimal colorings. AMS classification: 05C15, 05C38     

A sequence approach to linear perfect hash families

A linear (q ^d , q, t)-perfect hash family of size s in a vector space V of order q ^d over a field F of order q consists of a set of linear functionals from V to F with the following property: for all t subsets there exists such that is injective when restricted to F. A linear (q ^d , q, t)-perfect hash family of minimal size d(t − 1) is said to be optimal. In this paper, we extend the theory for linear perfect hash families based on sequences developed by Blackburn and Wild. We develop techniques which we use to construct new optimal linear (q ², q, 5)-perfect hash families and (q ⁴, q, 3)-perfect hash families. The sequence approach also explains a relationship between linear (q ³, q, 3)-perfect hash families and linear (q ², q, 4)-perfect hash families.      

Claw‐Free Graphs,Skeletal Graphs,and a Stronger Conjecture on ω, Δ, and χ

The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies . In this article, we prove that the conjecture holds for all claw‐free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way, we discuss a stronger local conjecture, and prove that it holds for claw‐free graphs with a three‐colorable complement. To prove our results, we introduce a very useful χ‐preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so‐called skeletal graphs.     

Extremal H‐Colorings of Graphs with Fixed Minimum Degree

For graphs G and H, a homomorphism from G to H, or H‐coloring of G, is a map from the vertices of G to the vertices of H that preserves adjacency. When H is composed of an edge with one looped endvertex, an H‐coloring of G corresponds to an independent set in G. Galvin showed that, for sufficiently large n, the complete bipartite graph is the n‐vertex graph with minimum degree δ that has the largest number of independent sets. In this article, we begin the project of generalizing this result to arbitrary H. Writing for the number of H‐colorings of G, we show that for fixed H and or , for any n‐vertex G with minimum degree δ (for sufficiently large n). We also provide examples of H for which the maximum is achieved by and other H for which the maximum is achieved by . For (and sufficiently large n), we provide an infinite family of H for which for any n‐vertex G with minimum degree δ. The results generalize to weighted H‐colorings.     

3‐Coloring Triangle‐Free Planar Graphs with a Precolored 8‐Cycle

Let G be a planar triangle‐free graph and let C be a cycle in G of length at most 8. We characterize all situations where a 3‐coloring of C does not extend to a proper 3‐coloring of the whole graph.     

Almost fifth powers in arithmetic progression

We prove that the product of k consecutive terms of a primitive arithmetic progression is never a perfect fifth power when 3?k?54. We also provide a more precise statement, concerning the case where the product is an “almost” fifth power. Our theorems yield considerable improvements and extensions, in the fifth power case, of recent results due to Gy?ry, Hajdu and Pintér. While the earlier results have been proved by classical (mainly algebraic number theoretical) methods, our proofs are based upon a new tool: we apply genus 2 curves and the Chabauty method (both the classical and the elliptic verison).     

Strong Chromatic Index of Sparse Graphs

A coloring of the edges of a graph G is strong if each color class is an induced matching of G. The strong chromatic index of G, denoted by , is the least number of colors in a strong edge coloring of G. Chang and Narayanan (J Graph Theory 73(2) (2013), 119–126) proved recently that for a 2‐degenerate graph G. They also conjectured that for any k‐degenerate graph G there is a linear bound , where c is an absolute constant. This conjecture is confirmed by the following three papers: in (G. Yu, Graphs Combin 31 (2015), 1815–1818), Yu showed that . In (M. Debski, J. Grytczuk, M. Sleszynska‐Nowak, Inf Process Lett 115(2) (2015), 326–330), D?bski, Grytczuk, and ?leszyńska‐Nowak showed that . In (T. Wang, Discrete Math 330(6) (2014), 17–19), Wang proved that . If G is a partial k‐tree, in (M. Debski, J. Grytczuk, M. Sleszynska‐Nowak, Inf Process Lett 115(2) (2015), 326–330), it is proven that . Let be the line graph of a graph G, and let be the square of the line graph . Then . We prove that if a graph G has an orientation with maximum out‐degree k, then has coloring number at most . If G is a k‐tree, then has coloring number at most . As a consequence, a graph with has , and a k‐tree G has .