The optimal general upper bound for the distinguishing index of infinite graphs

The distinguishing index $D\prime \left(G\right)$ of a graph $G$ is the least cardinal number $d$ such that $G$ has an edge-coloring with $d$ colors, which is preserved only by the trivial automorphism. We prove a general upper bound $D\prime \text{◂≤▸}\left(G\right)\le \mathrm{\Delta }-1$ for any connected infinite graph $G$ with finite maximum degree $\mathrm{\Delta }\ge 3$. This is in contrast with finite graphs since for every $\mathrm{\Delta }\ge 3$ there exist infinitely many connected, finite graphs $G$ with $\text{◂,▸}D\prime \left(G\right)=\mathrm{\Delta }$. We also give examples showing that this bound is sharp for any maximum degree $\mathrm{\Delta }$.     

Graph-like compacta: Characterizations and Eulerian loops

A compact graph-like space is a triple $\left(X,V,E\right)$, where $X$ is a compact, metrizable space, $V\subseteq X$ is a closed zero-dimensional subset, and $E$ is an index set such that $X⧹V\cong \text{◂+▸}E\times \left(0,1\right)$. New characterizations of compact graph-like spaces are given, connecting them to certain classes of continua, and to standard subspaces of Freudenthal compactifications of locally finite graphs. These are applied to characterize Eulerian graph-like compacta.     

Graph homomorphism reconfiguration and frozen H-colorings

We say that a graph $F$ strongly arrows a pair of graphs $\left(G,H\right)$ and write $\text{◂→▸}F\stackrel{\text{ind}}{\to }\left(G,H\right)$ if any coloring of its edges with red and blue leads to either a red $G$ or a blue $H$ appearing as induced subgraphs of $F$. The induced Ramsey number, $\text{◂...▸}\text{IR}\left(G,H\right)$, is defined as $\text{◂lim▸}\min \text{◂{}▸}\{|V\left(F\right)|:\text{◂→▸}F\stackrel{\text{ind}}{\to }\left(G,H\right)\}$. We consider the connection between the induced Ramsey number for a pair of two connected graphs $\text{◂...▸}\text{IR}\left(G,H\right)$ and the induced Ramsey number for multiple copies of these graphs $\text{IR}\text{◂()▸}\left(sG,tH\right)$, where $xG$ denotes the pairwise vertex-disjoint union of $x$ copies of $G$. It is easy to see that if $\text{◂→▸}F\stackrel{\text{ind}}{\to }\left(G,H\right)$, then $\text{◂⋅▸}\left(s+t-1\right)F\stackrel{\text{ind}}{\to }\text{◂()▸}\left(sG,tH\right)$. This implies that $$\text{◂...▸}\text{IR}\text{◂≤▸}\text{◂()▸}\left(sG,tH\right)\le \left(s+t-1\right)\text{IR}\left(G,H\right).$$ For several specific graphs, such as a path on three vertices vs a complete multipartite graph, a matching vs a complete graph, or a matching vs another matching, it is known that the above inequality is tight. On the other hand, the inequality is also strict for some graphs. However, even in the simplest case when $H$ is an edge and $t=2$, it is not known for what $G$ and for what $s$ the above inequality is tight. We show that it is tight if $G$ is connected and $s$ is at least as large as the order of $G$. In addition, we make further progress in determining induced Ramsey numbers for multiple copies of graphs, such as paths and triangles.     

Strong cliques in vertex-transitive graphs

A clique (resp, independent set) in a graph is strong if it intersects every maximal independent set (resp, every maximal clique). A graph is clique intersect stable set (CIS) if all of its maximal cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique $C$ in a vertex-transitive graph $\mathrm{\Gamma }$ is strong if and only if $\text{◂=▸}\text{◂⋅▸}\mid C\mid \mid I\mid =\mid V\left(\mathrm{\Gamma }\right)\mid$ for every maximal independent set $I$ of $\mathrm{\Gamma }$. On the basis of this result we prove that a vertex-transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex-transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of 5-valent vertex-transitive graphs admitting a strong clique. Our results imply that every vertex-transitive graph of valency at most 5 that admits a strong clique is localizable. We answer an open question by providing an example of a vertex-transitive CIS graph which is not localizable.     

A variant of the Erdős-Sós conjecture

A well-known conjecture of Erdős and Sós states that every graph with average degree exceeding $m-1$ contains every tree with $m$ edges as a subgraph. We propose a variant of this conjecture, which states that every graph of maximum degree exceeding $m$ and minimum degree at least $\lfloor 2m/3\rfloor$ contains every tree with $m$ edges. As evidence for our conjecture we show (a) for every $m$ there is a $g\left(m\right)$ such that the weakening of the conjecture obtained by replacing the first $m$ by $g\left(m\right)$ holds, and (b) there is a such that the weakening of the conjecture obtained by replacing $\lfloor 2m/3\rfloor$ by $\text{◂⋅▸}\left(1-\gamma \right)m$ holds.