Search

The natural extension of the concept of perfection in graphs to hypergraphs is to define a uniform m -hypergraph, H , as perfect , if it satisfies that for every subhypergraph H ′ , χ ( H ′ ) = ⌈ ω ( H ′ ) m − 1 ⌉ , where χ ( H ′ ) and ω ( H ′ ) are the chromatic and clique number of H ′ , respectively. It is known that comparability graphs are perfect. In this paper we introduce the concept of comparability 3-hypergraphs (those that can be transitively oriented) with the aim of proving that these are not perfect according to the natural definition. More explicitly, we exhibit three different subfamilies of comparability 3-hypergraphs which show different behaviors in respect to the relationship between the chromatic number and the clique number. [ABSTRACT FROM AUTHOR]

By considering graphs as topological spaces we introduce, at the level of homology, the notion of a null coloring, which provides new information on the task of clarifying the structure of cycles in a graph. We prove that for any graph G a maximal null coloring f is such that the quotient graph G / f is acyclic. As an application, for maximal planar graphs (sphere triangulations) of order n ≥ 4 , we prove that a vertex-coloring containing no rainbow faces uses at most ⌊ 2 n − 1 3 ⌋ colors, and this is best possible. For maximal graphs embedded on the projective plane we obtain the analogous best bound ⌊ 2 n + 1 3 ⌋ . [ABSTRACT FROM AUTHOR]

In this paper, we study the number of compact sets needed in an infinite family of convex sets with a local intersection structure to imply a bound on its piercing number, answering a conjecture of Erdős and Grünbaum. Namely, if in an infinite family of convex sets in $$\mathbb {R}^d$$ we know that out of every $$p$$ there are $$q$$ which are intersecting, we determine if having some compact sets implies a bound on the number of points needed to intersect the whole family. We also study variations of this problem. [ABSTRACT FROM AUTHOR]

Abstract: Let be an orthogonal array and let be an -coloring of its ground set . We give a combinatorial identity which relates the number of vectors in with given color patterns under with the cardinalities of the color classes. Several applications of the identity are considered. Among them it is shown that every coloring of an orthogonal array contains a positive proportion of almost rainbow vectors and also of almost monochromatic vectors of every color. [Copyright &y& Elsevier]

Abstract: Let be a prime number and be the cyclic group of order . A 3-coloring of is rainbow-free for some equation if it contains no rainbow solution of the equation. In  Jungić et al. (2003) proved that every 3-coloring of , with the cardinality of the smallest color class greater than four, has a rainbow solution of “almost” all linear equations in three variables in . In this work we handle the “small” cases and give a structural description of rainbow-free colorings for the particular case of , which includes the Schur equation. [Copyright &y& Elsevier]

Abstract: In this paper, we study homomorphisms of -edge-colored graphs, that is graphs with edges colored with two colors. We consider various graph classes (outerplanar graphs, partial 2-trees, partial -trees, planar graphs) and the problem is to find, for each class, the smallest number of vertices of a -edge-colored graph such that each graph of the considered class admits a homomorphism to . [Copyright &y& Elsevier]

Given a graph G on k edges, we consider the following two extremal problems: provided n is large enough, what is the minimum integer bal(n,G), if it exists, such that any 2‐coloring of the edges of a complete graph on n vertices having more than bal(n,G) edges in each color class, contains a balanced copy of G, that is, a copy of G with exactly ⌊k∕2⌋ edges in one of the colors? Graphs for which this is possible are called balanceable. The second problem deals with a similar question but we seek to guarantee copies of G in every tone, that is, having exactly r edges in, say, color red, for every 0≤r≤k. Graphs with this property are called omnitonal. We study these problems for different graph families, including paths, stars, and trees in general. When studying such extremal parameters, the question of its existence is obliged. In this line, two universal unavoidable patterns in 2‐edge‐colorings of the complete graph with sufficient representation in each of the colors emerge naturally and they are the key to characterizing balanceable as well as omnitonal graphs. For the two universal unavoidable patterns, which were already known to exist via a Ramsey‐theoretic approach, we present here a Turán‐type counterpart. [ABSTRACT FROM AUTHOR]

For an integer d ≥ 2 which is not a square, we show that there is at most one value of the positive integer X participating in the Pell equation X 2 − d Y 2 = ± 1 which is a product of two Fibonacci numbers, with a few exceptions that we completely characterize. [ABSTRACT FROM AUTHOR]

We prove the following results solving a problem raised by Caro and Yuster (Graphs Comb 32:49–63, 2016). For a positive integer m ≥ 2 , m ≠ 4 , there are infinitely many values of n such that the following holds: There is a weighting function f : E (K n) → { - 1 , 1 } (and hence a weighting function f : E (K n) → { - 1 , 0 , 1 } ), such that ∑ e ∈ E (K n) f (e) = 0 but, for every copy H of K m in K n , ∑ e ∈ E (H) f (e) ≠ 0 . On the other hand, for every integer n ≥ 5 and every weighting function f : E (K n) → { - 1 , 1 } such that | ∑ e ∈ E (K n) f (e) | ≤ n 2 - 2 h (n) , where h (n) = (n + 1) if n ≡ 0 (mod 4) and h (n) = n if n ≢ 0 (mod 4), there is always a copy H of K 4 in K n for which ∑ e ∈ E (H) f (e) = 0 , and the value of h(n) is sharp. [ABSTRACT FROM AUTHOR]

Abstract The following result gives the flavor of this paper: Let t , k and q be integers such that q ≥ 0 , 0 ≤ t < k and t ≡ k (mod 2) , and let s ∈ [ 0 , t + 1 ] be the unique integer satisfying s ≡ q + k − t − 2 2 (mod (t + 2)). Then for any integer n such that n ≥ max ⁡ { k , 1 2 (t + 2) k 2 + q − s t + 2 k − t 2 + s } and any function f : [ n ] → { − 1 , 1 } with | ∑ i = 1 n f (i) | ≤ q , there is a set B ⊆ [ n ] of k consecutive integers with | ∑ y ∈ B f (y) | ≤ t. Moreover, this bound is sharp for all the parameters involved and a characterization of the extremal sequences is given. This and other similar results involving different subsequences are presented, including decompositions of sequences into subsequences of bounded weight. [ABSTRACT FROM AUTHOR]

We study vertex colorings of hypergraphs, such that all color sizes differ at most in one (balanced colorings) and each edge contains at least two vertices of the same color (rainbow-free colorings). Given a hypergraph H , the maximum k , such that there is a balanced rainbow-free k -coloring of H is called the balanced upper chromatic number denoted by χ ¯ b ( H ) . Concerning hypergraphs defined by projective spaces, bounds on the balanced upper chromatic number and constructions of rainbow-free colorings are given. For cyclic projective planes of order q we prove that: q 2 + q + 1 6 ≤ χ ¯ b ( Π q ) ≤ q 2 + q + 1 3 . We also give bounds for the balanced upper chromatic numbers of the hypergraphs arising from the n -dimensional finite space PG ( n , q ) . [ABSTRACT FROM AUTHOR]

Let G be a simple n‐vertex graph and c be a coloring of E(G) with n colors, where each color class has size at least 2. We prove that (G,c) contains a rainbow cycle of length at most ⌈n2⌉, which is best possible. Our result settles a special case of a strengthening of the Caccetta‐Häggkvist conjecture, due to Aharoni. We also show that the matroid generalization of our main result also holds for cographic matroids, but fails for binary matroids. [ABSTRACT FROM AUTHOR]

Let { p 1 , ... , p n } and { q 1 , ... , q n } be two sets of n labeled points in general position in the plane. We say that these two point sets have the same order type if for every triple of indices (i , j , k) , p k is above the directed line from p i to p j if and only if q k is above the directed line from q i to q j. In this paper we give the first non-trivial lower bounds on the number of different order types of n points that can be realized in integer grids of polynomial size. [ABSTRACT FROM AUTHOR]