Color-blind index in graphs of very low degree

Let $c:E(G)to [k]$ be an edge-coloring of a graph $G$, not necessarily proper. For each vertex $v$, let $bar{c}(v)=(a_1,ldots,a_k)$, where $a_i$ is the number of edges incident to $v$ with color $i$. Reorder $bar{c}(v)$ for every $v$ in $G$ in nonincreasing order to obtain $c^*(v)$, the color-blind partition of $v$. When $c^*$ induces a proper vertex coloring, that is, $c^*(u) eq c^*(v)$ for every edge $uv$ in $G$, we say that $c$ is color-blind distinguishing. The minimum $k$ for which there exists a color-blind distinguishing edge coloring $c:E(G)to [k]$ is the color-blind index of $G$, denoted $operatorname{dal}(G)$. We demonstrate that determining the color-blind index is more subtle than previously thought. In particular, determining if $operatorname{dal}(G) leq 2$ is NP-complete. We also connect the color-blind index of a regular bipartite graph to 2-colorable regular hypergraphs and characterize when $operatorname{dal}(G)$ is finite for a class of 3-regular graphs.

Extending Precolorings to Distinguish Group Actions

Given a group $Gamma$ acting on a set $X$, a $k$-coloring $phi:Xto{1,dots,k}$ of $X$ is distinguishing with respect to $Gamma$ if the only $gammain Gamma$ that fixes $phi$ is the identity action. The distinguishing number of the action $Gamma$, denoted $D_{Gamma}(X)$, is then the smallest positive integer $k$ such that there is a distinguishing $k$-coloring of $X$ with respect to $Gamma$. This notion has been studied in a number of settings, but by far the largest body of work has been concerned with finding the distinguishing number of the action of the automorphism group of a graph $G$ upon its vertex set, which is referred to as the distinguishing number of $G$. The distinguishing number of a group action is a measure of how difficult it is to break all of the permutations arising from that action. In this paper, we aim to further differentiate the resilience of group actions with the same distinguishing number. In particular, we introduce a precoloring extension framework to address this issue. A set $S subseteq X$ is a fixing set for $Gamma$ if for every non-identity element $gamma in Gamma$ there is an element $s in S$ such that $gamma(s) eq s$. The distinguishing extension number $operatorname{ext}_D(X,Gamma;k)$ is the minimum number $m$ such that for all fixing sets $W subseteq X$ with $|W| geq m$, every $k$-coloring $c : X setminus W to [k]$ can be extended to a $k$-coloring that distinguishes $X$. In this paper, we prove that $operatorname{ext}_D(mathbb{R},operatorname{Aut}(mathbb{R}),2) =4$, where $operatorname{Aut}(mathbb{R})$ is comprised of compositions of translations and reflections. We also consider the distinguishing extension number of the circle and (finite) cycles, obtaining several exact results and bounds.

On the independence ratio of distance graphs

A distance graph is an undirected graph on the integers where two integers are adjacent if their difference is in a prescribed distance set. The independence ratio of a distance graph $G$ is the maximum density of an independent set in $G$. Lih, Liu, and Zhu [Star extremal circulant graphs, SIAM J. Discrete Math. 12 (1999) 491--499] showed that the independence ratio is equal to the inverse of the fractional chromatic number, thus relating the concept to the well studied question of finding the chromatic number of distance graphs. We prove that the independence ratio of a distance graph is achieved by a periodic set, and we present a framework for discharging arguments to demonstrate upper bounds on the independence ratio. With these tools, we determine the exact independence ratio for several infinite families of distance sets of size three, determine asymptotic values for others, and present several conjectures.