Yair Caro

Connected Turán number of trees

As a variant of the much studied Turán number, $ex(n,F)$ , the largest number of edges that an $n$ -vertex $F$ -free graph may contain, we introduce the connected Turán number $ex_c(n,F)$ , the largest number of edges that an $n$ -vertex connected $F$ -free graph may contain. We focus on the case where the forbidden graph is a tree. The celebrated conjecture of Erdős and Sós states that for any tree $T$ , we have $ex(n,T)\le(|T|-2)\frac{n}{2}$ . We address the problem how much smaller $ex_c(n,T)$ can be, what is the smallest possible ratio of $ex_c(n,T)$ and $(|T|-2)\frac{n}{2}$ as $|T|$ grows. We also determine the exact value of $ex_c(n,T)$ for small trees, in particular for all trees with at most six vertices. We introduce general constructions of connected $T$ -free graphs based on graph parameters as longest path, matching number, branching number, etc.

Higher Degree Davenport Constants over Finite Commutative Rings

We generalize the notion of Davenport constants to a `higher degree' and obtain various lower and upper bounds, which are sometimes exact as is the case for certain finite commutative rings of prime power cardinality. Two simple examples that capture the essence of these higher degree Davenport constants are the following. 1) Suppose $n = 2^k$ , then every sequence of integers $S$ of length $2n$ contains a subsequence $S'$ of length at least two such that $\sum_{a_i,a_j \in S'} a_ia_j \equiv 0 \pmod{n}$ and the bound is sharp. 2) Suppose $n \equiv1 \pmod{2}$ , then every sequence of integers $S$ of length $2n -1$ contains a subsequence $S'$ of length at least two such that $\sum_{a_i,a_j \in S'} a_ia_j \equiv 0 \pmod{n}$ . These examples illustrate that if a sequence of elements from a finite commutative ring is long enough, certain symmetric expressions have to vanish on the elements of a subsequence.

Higher Degree Erdos-Ginzburg-Ziv Constants

We generalize the notion of Erdős-Ginzburg-Ziv constants -- along the same lines we generalized in earlier work the notion of Davenport constants -- to a ``higher degree" and obtain various lower and upper bounds. These bounds are sometimes exact as is the case for certain finite commutative rings of prime power cardinality. We also consider to what extent a theorem due independently to W.D.~Gao and the first author that relates these two parameters extends to this higher degree setting. Two simple examples that capture the essence of these higher degree Erdős-Ginzburg-Ziv constants are the following. 1) Let $ν_p(m)$ denote the $p-$ adic valuation of the integer $m$ . Suppose we have integers $t | {m \choose 2}$ and $n=t+2^{ν_2(m)}$ , then every sequence $S$ over ${\mathbb Z}_2$ of length $|S| \geq n$ contains a subsequence $S'$ of length $t$ for which $\sum_{a_{i_1},\ldots, a_{i_m} \in S'} a_{i_1}\cdots a_{i_m} \equiv 0 \pmod{2}$ , and this is sharp. 2) Suppose $k=3^α$ for some integer $α\geq 2$ . Then every sequence $S$ over ${\mathbb Z}_3$ of length $|S| \geq k+6$ contains a subsequence $S'$ of length $k$ for which $\sum_{a_h, a_i, a_j \in S'} a_ha_ia_j \equiv 0 \pmod{3}$ . These examples illustrate that if a sequence of elements from a finite commutative ring is long enough, certain symmetric expressions (symmetric polynomials) have to vanish on the elements of a subsequence of prescribed length. The Erdős-Ginzburg-Ziv Theorem is just the case where a sequence of length $2n-1$ over ${\mathbb Z}_n$ contains a subsequence $S'=(a_1, \ldots, a_n)$ of length $n$ that vanishes when substituted in the linear symmetric polynomial $a_1+\cdots+a_n.$

Index of Parameters of Iterated Line Graphs

Let $G$ be a prolific graph, that is a finite connected simple graph which is not isomorphic to a cycle nor a path nor the star graph $K_{1,3}$ . The line-graph of $G$ , denoted by $L(G)$ , is defined by having its vertex-set equal to the edge-set of $G$ and two vertices of $L(G)$ are adjacent if the corresponding edges are adjacent in $G$ . For a positive integer $k$ , the iterated line-graph $L^k(G)$ is defined recursively by $L^k(G)=L(L^{k-1}(G))$ . We consider fifteen graph parameters and study their behaviour when the operation of taking the line-graph is iterated. We shall first show that all of these parameters are unbounded. This idea is motivated by a well-known result of van Rooij and Wilf that says that the number of vertices is unbounded if and only if the graph is prolific. We then study of the value of $k(P,{\mathcal F})$ , which is the index of a family of prolific graphs with regards to a given graph parameter $P(G)$ . For a given parameter $P(G)$ , the index of $G$ is denoted by $ind(P,G) = \min \{ r : P(G) < P(L^r(G) \}$ . Now for a family $\mathcal F$ of prolific graphs, the index of the family is $k(P,\mathcal{F}) = \max \{ ind(P,G) : G \in \mathcal F\}$ . The problem of determining the index of a parameter over the family of prolific graphs is motivated by a result of Chartrand who showed that it could require $k=|V(G)|-3$ iterations for $L^k(G)$ to have a hamiltonian cycle. For twelve of the parameters considered, we exactly determine $k(P,\mathcal F)$ where $\mathcal F$ is the family of all prolific graphs, and for some parameters we also characterize the class of prolific graphs realizing the extremal value $k(P,\mathcal F$ ). Interesting open problems remain, in particular completing the determination of $k(P,\mathcal F)$ for the three parameters: the independence number, independent domination number and domination number.

Remarks on odd colorings of graphs

A proper vertex coloring $φ$ of graph $G$ is said to be odd if for each non-isolated vertex $x\in V(G)$ there exists a color $c$ such that $φ^{-1}(c)\cap N(x)$ is odd-sized. The minimum number of colors in any odd coloring of $G$ , denoted $χ_o(G)$ , is the odd chromatic number. Odd colorings were recently introduced in [M.~Petruševski, R.~Škrekovski: \textit{Colorings with neighborhood parity condition}]. Here we discuss various basic properties of this new graph parameter, characterize acyclic graphs and hypercubes in terms of odd chromatic number, establish several upper bounds in regard to degenericity or maximum degree, and pose several questions and problems.

Remarks on proper conflict-free colorings of graphs

A vertex coloring of a graph is said to be \textit{conflict-free} with respect to neighborhoods if for every non-isolated vertex there is a color appearing exactly once in its (open) neighborhood. As defined in [Fabrici et al., \textit{Proper Conflict-free and Unique-maximum Colorings of Planar Graphs with Respect to Neighborhoods}, arXiv preprint], the minimum number of colors in any such proper coloring of graph $G$ is the PCF chromatic number of $G$ , denoted $χ_{\mathrm{pcf}}(G)$ . In this paper, we determine the value of this graph parameter for several basic graph classes including trees, cycles, hypercubes and subdivisions of complete graphs. We also give upper bounds on $χ_{\mathrm{pcf}}(G)$ in terms of other graph parameters. In particular, we show that $χ_{\mathrm{pcf}}(G) \leq5Δ(G)/2$ and characterize equality. Several sufficient conditions for PCF $k$ -colorability of graphs are established for $4\le k\le 6$ . The paper concludes with few open problems.

The feasibility problem for line graphs

We consider the following feasibility problem: given an integer $n \geq 1$ and an integer $m$ such that $0 \leq m \leq \binom{n}{2}$ , does there exist a line graph $L = L(G)$ with exactly $n$ vertices and $m$ edges ? We say that a pair $(n,m)$ is non-feasible if there exists no line graph $L(G)$ on $n$ vertices and $m$ edges, otherwise we say $(n,m)$ is a feasible pair. Our main result shows that for fixed $n\geq 5$ , the values of $m$ for which $(n, m)$ is a non-feasible pair, form disjoint blocks of consecutive integers which we completely determine. On the other hand we prove, among other things, that for the more general family of claw-free graphs (with no induced $K_{1,3}$ -free subgraph), all $(n,m)$ -pairs in the range $0 \leq m \leq \binom{n}{2}$ are feasible pairs.

preprint2021arXiv

Sum-distinguishing number of sparse hypergraphs

A vertex labeling of a hypergraph is sum distinguishing if it uses positive integers and the sums of labels taken over the distinct hyperedges are distinct. Let s(H) be the smallest integer N such that there is a sum-distinguishing labeling of H with each label at most N. The largest value of s(H) over all hypergraphs on n vertices and m hyperedges is denoted s(n,m). We prove that s(n,m) is almost-quadratic in m as long as m is not too large. More precisely, the following holds: If n < m < n^{O(1)} then s(n,m)= m^2/w(m), where w(m) is a function that goes to infinity and is smaller than any polynomial in m. The parameter s(n,m) has close connections to several other graph and hypergraph functions, such as the irregularity strength of hypergraphs. Our result has several applications, notably: 1. We answer a question of Gyarfas et al. whether there are n-vertex hypergraphs with irregularity strength greater than 2n. In fact we show that there are n-vertex hypergraphs with irregularity strength at least n^{2-o(1)}. 2. Our results imply that s*(n)=n^2/w(n) where s*(n) is the distinguishing closed-neighborhood number, i.e., the smallest integer N such that any n-vertex graph allows for a vertex labeling with positive integers at most N so that the sums of labels on distinct closed neighborhoods of vertices are distinct.

preprint2020arXiv

On small balanceable, strongly-balanceable and omnitonal graphs

In Ramsey theory for graphs we are given a graph $G$ and we are required to find the least $n_0$ such that, for any $n\geq n_0$ , any red/blue colouring of the edges of $K_n$ gives a subgraph $G$ all of whose edges are blue or all are red. Here we shall be requiring that, for any red/blue colouring of the edges of $K_n$ , there must be a copy of $G$ such that its edges are partitioned equally as red or blue (or the sizes of the colour classes differs by one in the case when $G$ has an odd number of edges). This introduces the notion of balanceable graphs and the balance number of $G$ which, if it exists, is the minimum integer bal $(n, G)$ such that, for any red/blue colouring of $E(K_n)$ with more than bal $(n, G)$ edges of either colour, $K_n$ will contain a balanced coloured copy of $G$ as described above. This parameter was introduced by Caro, Hansberg and Montejano in \cite{2018arXivCHM}. There, the authors also introduce the strong balance number sbal $(n,G)$ and the more general omnitonal number ot $(n, G)$ which requires copies of $G$ containing a complete distribution of the number of red and blue edges over $E(G)$ . In this paper we shall catalogue bal $(n, G)$ , sbal $(n, G)$ and ot $(n,G)$ for all graphs $G$ on at most four edges. We shall be using some of the key results of Caro et al, which we here reproduce in full, as well as some new results which we prove here. For example, we shall prove that the union of two bipartite graphs with the same number of edges is always balanceable.

preprint2020arXiv

On zero-sum spanning trees and zero-sum connectivity

We consider $2$ -colourings $f : E(G) \rightarrow \{ -1 ,1 \}$ of the edges of a graph $G$ with colours $-1$ and $1$ in $\mathbb{Z}$ . A subgraph $H$ of $G$ is said to be a zero-sum subgraph of $G$ under $f$ if $f(H) := \sum_{e\in E(H)} f(e) =0$ . We study the following type of questions, in several cases obtaining best possible results: Under which conditions on $|f(G)|$ can we guarantee the existence of a zero-sum spanning tree of $G$ ? The types of $G$ we consider are complete graphs, $K_3$ -free graphs, $d$ -trees, and maximal planar graphs. We also answer the question of when any such colouring contains a zero-sum spanning path or a zero-sum spanning tree of diameter at most $3$ , showing in passing that the diameter- $3$ condition is best possible. Finally, we give, for $G = K_n$ , a sharp bound on $|f(K_n)|$ by which an interesting zero-sum connectivity property is forced, namely that any two vertices are joined by a zero-sum path of length at most $4$ . One feature of this paper is the proof of an Interpolation Lemma leading to a Master Theorem from which many of the above results follow and which can be of independent interest.

preprint2016arXiv

Two short proofs of the Perfect Forest Theorem

A perfect forest is a spanning forest of a connected graph $G$ , all of whose components are induced subgraphs of $G$ and such that all vertices have odd degree in the forest. A perfect forest generalised a perfect matching since, in a matching, all components are trees on one edge. Scott first proved the Perfect Forest Theorem, namely, that every connected graph of even order has a perfect forest. Gutin then gave another proof using linear algebra. We give here two very short proofs of the Perfect Forest Theorem which use only elementary notions from graph theory. Both our proofs yield polynomial-time algorithms for finding a perfect forest in a connected graph of even order.

preprint2016arXiv

Zero-sum subsequences in bounded-sum $\{-1, 1\}$ -sequences

The following result gives the flavor of this paper: Let $t$ , $k$ and $q$ be integers such that $q\geq 0$ , $0\leq t < k$ and $t \equiv k \,({\rm mod}\, 2)$ , and let $s\in [0,t+1]$ be the unique integer satisfying $s \equiv q + \frac{k-t-2}{2} \,({\rm mod} \, (t+2))$ . Then for any integer $n$ such that $n \ge \max\left\{k,\frac{1}{2(t+2)}k^2 + \frac{q-s}{t+2}k - \frac{t}{2} + s\right\}$ and any function $f:[n]\to \{-1,1\}$ with $|\sum_{i=1}^nf(i)| \le q$ , there is a set $B \subseteq [n]$ of $k$ consecutive integers with $|\sum_{y\in B}f(y)| \le 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.

Partial domination - the isolation number of a graph

We prove the following result: If $G$ be a connected graph on $n \ge 6$ vertices, then there exists a set of vertices $D$ with $|D| \le \frac{n}{3}$ and such that $V(G) \setminus N[D]$ is an independent set, where $N[D]$ is the closed neighborhood of $D$ . Furthermore, the bound is sharp. This seems to be the first result in the direction of partial domination with constrained structure on the graph induced by the non-dominated vertices, which we further elaborate in this paper.

Ramsey numbers for degree monotone paths

A path $v_1,v_2,\ldots,v_m$ in a graph $G$ is $degree$ - $monotone$ if $deg(v_1) \leq deg(v_2) \leq \cdots \leq deg(v_m)$ where $deg(v_i)$ is the degree of $v_i$ in $G$ . Longest degree-monotone paths have been studied in several recent papers. Here we consider the Ramsey type problem for degree monotone paths. Denote by $M_k(m)$ the minimum number $M$ such that for all $n \geq M$ , in any $k$ -edge coloring of $K_n$ there is some $1\leq j \leq k$ such that the graph formed by the edges colored $j$ has a degree-monotone path of order $m$ . We prove several nontrivial upper and lower bounds for $M_k(m)$ .

Regular independent sets

The regular independence number, introduced by Albertson and Boutin in 1990, is the size of a largest set of independent vertices with the same degree. Lower bounds were proven for this invariant, in terms of the order, for trees and planar graphs. In this article, we generalize and extend these results to find lower bounds for the regular $k$ -independence number for trees, forests, planar graphs, $k$ -trees and $k$ -degenerate graphs.

Selective Hypergraph Colourings

We look at colourings of $r$ -uniform hypergraphs, focusing our attention on unique colourability and gaps in the chromatic spectrum. The pattern of an edge $E$ in an $r$ -uniform hypergraph $H$ whose vertices are coloured is the partition of $r$ induced by the colour classes of the vertices in $E$ . Let $Q$ be a set of partitions of $r$ . A $Q$ -colouring of $H$ is a colouring of its vertices such that only patterns appearing in $Q$ are allowed. We first show that many known hypergraph colouring problems, including Ramsey theory, can be stated in the language of $Q$ -colourings. Then, using as our main tools the notions of $Q$ -colourings and $Σ$ -hypergraphs, we define and prove a result on tight colourings, which is a strengthening of the notion of unique colourability. $Σ$ -hypergraphs are a natural generalisation of $σ$ -hypergraphs introduced by the first two authors in an earlier paper. We also show that there exist $Σ$ -hypergraphs with arbitrarily large $Q$ -chromatic number and chromatic number but with bounded clique number. Dvorak et al. have characterised those $Q$ which can lead to a hypergraph with a gap in its $Q$ -spectrum. We give a short direct proof of the necessity of their condition on $Q$ . We also prove a partial converse for the special case of $Σ$ -hypergraphs. Finally, we show that, for at least one family $Q$ which is known to yield hypergraphs with gaps, there exist no $Σ$ -hypergraphs with gaps in their $Q$ -spectrum.

$(2,2)$ -colourings and clique-free $σ$ -hypergraphs

We consider vertex colourings of $r$ -uniform hypergraphs $H$ in the classical sense, that is such that no edge has all its vertices given the same colour, and $(2,2)$ -colourings of $H$ in which the vertices in any edge are given exactly two colours. This is a special case of constrained colourings introduced by Bujtas and Tuza which, in turn, is a generalisation of Voloshin's colourings of mixed hypergraphs. We study, $χ(H)$ , the classical chromatic number, and the $(2,2)$ -spectrum of $H$ , that is, the set of integers $k$ for which $H$ has a $(2,2)$ -colouring using exactly $k$ colours. We present extensions of hypergraphs which preserve both the chromatic number and the $(2,2)$ -spectrum and which, however often repeated, do not increase the clique number of $H$ by more than a fixed number. In particular, we present sparse $(2,2)$ -colourable clique-free $σ$ -hypergraphs having arbitrarily large chromatic number - these $r$ -uniform hypergraphs were studied by the authors in earlier papers. We use these ideas to extend some known $3$ -uniform hypergraphs which exhibit a $(2,2)$ -spectrum with remarkable gaps. We believe that this work is the first to present an extension of hypergraphs which preserves both $χ(H)$ and the $(2,2)$ -spectrum of $H$ simultaneously.

Constrained colouring and $σ$ -hypergraphs

A constrained colouring or, more specifically, an $(α,β)$ -colouring of a hypergraph $H$ , is an assignment of colours to its vertices such that no edge of $H$ contains less than $α$ or more than $β$ vertices with different colours. This notion, introduced by B{ú}jtas and Tuza, generalises both classical hypergraph colourings and the more general Voloshin colourings of hypergraphs. In fact, for $r$ -uniform hypergraphs, classical colourings correspond to $(2,r)$ -colourings while an important instance of Voloshin colourings of $r$ -uniform hypergraphs gives $(2, r-1)$ -colourings. One intriguing aspect of all these colourings, not present in classical colourings, is that $H$ can have gaps in its $(α,β)$ -spectrum, that is, for $k_1 < k_2 < k_3$ , $H$ would be $(α,β)$ -colourable using $k_1$ and using $k_3$ colours, but not using $k_2$ colours. In an earlier paper, the first two authors introduced, for $σ$ a partition of $r$ , a very versatile type of $r$ -uniform hypergraph which they called $σ$ -hypergraphs. They showed that, by simple manipulation of the parameters of a $σ$ -hypergraph $H$ , one can obtain families of hypergraphs which have $(2,r-1)$ -colourings exhibiting various interesting chromatic properties. They also showed that, if the smallest part of $σ$ is at least 2, then $H$ will never have a gap in its $(2,r-1)$ -spectrum but, quite surprisingly, they found examples where gaps re-appear when $α=β=2$ . In this paper we extend many of the results of the first two authors to more general $(α,β)$ -colourings, and we study the phenomenon of the disappearanace and re-appearance of gaps and show that it is not just the behaviour of a particular example but we place it within the context of a more general study of constrained colourings of $σ$ -hypergraphs.

Degree Monotone Paths

We shall study degree-monotone paths in graphs, a problem inspired by the celebrated theorem of Erd{ő}s-Szekeres concerning the longest monotone subsequence of a given sequence of numbers. A path P in a graph G is said to be a degree monotone path if the sequence of degrees of the vertices in P in the order they appear in P is monotonic. In this paper we shall consider these three problem related to this parameter: 1. Find bounds on $mp(G)$ in terms of other parameters of $G$ . 2. Study $f(n,k)$ defined to be the maximum number of edges in a graph on $n$ vertices with $mp(G) < k$ . 3. Estimate the minimum and the maximum over all graph $G$ on $n$ vertices of $mp(G)+mp(\overline{G})$ . For the first problem our main tool will be the Gallai-Roy Theorem on directed paths and chromatic number. We shall also consider in some detail maximal planar and maximal outerplanar graphs in order to investigate the sharpness of the bounds obtained. For the second problem we establish a close link between $f(n,k)$ and the classical Turan numbers. For the third problem we establish some Nordhaus-Gaddum type of inequalities. We conclude by indicating some open problems which our results point to.

Degree Monotone Paths and Graph Operations

A path $P$ in a graph $G$ is said to be a degree monotone path if the sequence of degrees of the vertices of $P$ in the order in which they appear on $P$ is monotonic. The length of the longest degree monotone path in $G$ is denoted by $mp(G)$ . This parameter was first studied in an earlier paper by the authors where bounds in terms of other parameters of $G$ were obtained. In this paper we concentrate on the study of how $mp(G)$ changes under various operations on $G$ . We first consider how $mp(G)$ changes when an edge is deleted, added, contracted or subdivided. We similarly consider the effects of adding or deleting a vertex. We sometimes restrict our attention to particular classes of graphs. Finally we study $mp(G \times H)$ in terms of $mp(G)$ and $mp(H)$ where $\times$ is either the Cartesian product or the join of two graphs. In all these cases we give bounds on the parameter $mp$ of the modified graph in terms of the original graph or graphs and we show that all the bounds are sharp.

Dynamic approach to k-forcing

The k-forcing number of a graph is a generalization of the zero forcing number. In this note, we give a greedy algorithm to approximate the k-forcing number of a graph. Using this dynamic approach, we give corollaries which improve upon two theorems from a recent paper of Amos, Caro, Davila and Pepper [2], while also answering an open problem posed by Meyer [9].

Independence and Matchings in $σ$ -hypergraphs

Let $σ$ be a partition of the positive integer $r$ . A $σ$ -hypergraph $H=H(n,r,q|σ)$ is an $r$ -uniform hypergraph on $nq$ vertices which are partitioned into $n$ classes $V_1, V_2, \ldots, V_n$ each containing $q$ vertices. An $r$ -subset $K$ of vertices is an edge of the hypergraph if the partition of $r$ formed by the non-zero cardinalities $|K\cap V_i|, 1\leq i \leq n,$ is $σ$ . In earlier works we have considered colourings of the vertices of $H$ which are constrained such that any edge has at least $α$ and at most $β$ vertices of the same colour, and we have shown that interesting results can be obtained by varying $α, β$ and the parameters of $H$ appropriately. In this paper we continue to investigate the versatility of $σ$ -hypergraphs by considering two classical problems: independence and matchings. We first demonstrate an interesting link between the constrained colourings described above and the $k$ -independence number of a hypergraph, that is, the largest cardinality of a subset of vertices of a hypergraph not containing $k+1$ vertices in the same edge. We also give an exact computation of the $k$ -independence number of the $σ$ -hypergraph $H$ . We then present results on maximum, and sometimes perfect, matchings in $H$ . These results often depend on divisibility relations between the parameters of $H$ and on the highest common factor of the parts of $σ$ .

The Saturation Number for the length of Degree Monotone Paths

A degree monotone path in a graph $G$ is a path $P$ such that the sequence of degrees of the vertices in the order in which they appear on $P$ is monotonic. The length of the longest degree monotone path in $G$ is denoted by $mp(G)$ . This parameter, inspired by the well-known Erdos-Szekeres theorem, has been studied by the authors in two earlier papers. Here we consider a saturation problem for the parameter $mp(G)$ . We call $G$ saturated if, for every edge $e$ added to $G$ , $mp(G+e) >mp(G)$ , and we define $h(n,k)$ to be the least possible number of edges in a saturated graph $G$ on $n$ vertices with $mp(G) < k$ , while $mp(G+e) \geq k$ for every new edge $e$ . We obtain linear lower and upper bounds for $h(n,k)$ , we determine exactly the values of $h(n,k)$ for $k=3$ and $4$ , and we present constructions of saturated graphs.