More Like this

1. Leibniz International Proceedings in Informatics (LIPIcs):32nd International Symposium on Algorithms and Computation (ISAAC 2021)

   https://doi.org/10.4230/LIPIcs.ISAAC.2021.5  

   Gibson-Lopez, Matt; Yang, Zhongxiu (November 2021, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Ahn, Hee-Kap; Sadakane, Kunihiko (Ed.)

   Visibility problems are fundamental to computational geometry, and many versions of geometric set cover where coverage is based on visibility have been considered. In most settings, points can see "infinitely far" so long as visibility is not "blocked" by some obstacle. In many applications, this may be an unreasonable assumption. In this paper, we consider a new model of visibility where no point can see any other point beyond a sight radius ρ. In particular, we consider this visibility model in the context of terrains. We show that the VC-dimension of limited visibility terrains is exactly 7. We give lower bound construction that shatters a set of 7 points, and we prove that shattering 8 points is not possible. 

   more » « less
2. Hyperbolic families and coloring graphs on surfaces

   https://doi.org/https://doi.org/10.1090/btran/26  

   Postle, Luke; Thomas, Robin (December 2018, Transactions of the American Mathematical Society. Series B)

   We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $$ \Sigma $$ of genus $ g$ and let $$ L=(L(v):v\in V(G))$$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $$ \phi $$ with domain $ V(G)$ such that $$ \phi (v)\in L(v)$$ for every $$ v\in V(G)$$ and $$ \phi (v)\ne \phi (u)$$ for every pair of adjacent vertices $$ u,v\in V(G)$$. We prove if every non-null-homotopic cycle in $ G$ has length $$ \Omega (\log g)$$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $$ \vert V(G)\vert=O(g)$$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and a set $$ X\subseteq V(G)$$ of vertices that are pairwise at distance $$ \Omega (1)$$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $$ \Omega (1)$$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $$ 2^{\Omega (\vert V(G)\vert)}$$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities. 

   more » « less
3. Characterization of All Graphs with a Failed Skew Zero Forcing Number of 1

   https://doi.org/10.3390/math10234463  

   Johnson, Aidan; Vick, Andrew E.; Narayan, Darren A. (December 2022, Mathematics)

   Given a graph G, the zero forcing number of G, Z(G), is the minimum cardinality of any set S of vertices of which repeated applications of the forcing rule results in all vertices being in S. The forcing rule is: if a vertex v is in S, and exactly one neighbor u of v is not in S, then u is added to S in the next iteration. Hence the failed zero forcing number of a graph was defined to be the cardinality of the largest set of vertices which fails to force all vertices in the graph. A similar property called skew zero forcing was defined so that if there is exactly one neighbor u of v is not in S, then u is added to S in the next iteration. The difference is that vertices that are not in S can force other vertices. This leads to the failed skew zero forcing number of a graph, which is denoted by F−(G). In this paper, we provide a complete characterization of all graphs with F−(G)=1. Fetcie, Jacob, and Saavedra showed that the only graphs with a failed zero forcing number of 1 are either: the union of two isolated vertices; P3; K3; or K4. In this paper, we provide a surprising result: changing the forcing rule to a skew-forcing rule results in an infinite number of graphs with F−(G)=1. 

   more » « less
4. On 2-fold graceful graphs

   Bunge, R; Cornett, M; El-Zanati, S; Jeffries, J; Rattin, E. (January 2020, Journal of Combinatorial Mathematics and Combinatorial Computing)

   null (Ed.)

   A long-standing conjecture by Kotzig, Ringel, and Rosa states that every tree admits a graceful labeling. That is, for any tree $$T$$ with $$n$$~edges, it is conjectured that there exists a labeling $$f\colon V(T) \to \{0,1,\ldots,n\}$$ such that the set of induced edge labels $$\bigl\{ |f(u)-f(v)| : \{u,v\}\in E(T) \bigr\}$$ is exactly $$\{1,2,\ldots,n\}$$. We extend this concept to allow for multigraphs with edge multiplicity at most~$$2$$. A \emph{2-fold graceful labeling} of a graph (or multigraph) $$G$$ with $$n$$~edges is a one-to-one function $$f\colon V(G) \to \{0,1,\ldots,n\}$$ such that the multiset of induced edge labels is comprised of two copies of each element in $$\bigl\{ 1,2,\ldots, \lfloor n/2 \rfloor \bigr\}$$ and, if $$n$$ is odd, one copy of $$\bigl\{ \lceil n/2 \rceil \bigr\}$$. When $$n$$ is even, this concept is similar to that of 2-equitable labelings which were introduced by Bloom and have been studied for several classes of graphs. We show that caterpillars, cycles of length $$n \not\equiv 1 \pmod{4}$$, and complete bipartite graphs admit 2-fold graceful labelings. We also show that under certain conditions, the join of a tree and an empty graph (i.e., a graph with vertices but no edges) is $$2$$-fold graceful. 

   more » « less
5. Pure Pairs. V. Excluding Some Long Subdivision

   https://doi.org/10.1007/s00493-023-00025-8  

   Scott, Alex; Seymour, Paul; Spirkl, Sophie (June 2023, Combinatorica)

   A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε>0, there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with |A|,|B|≥εn. He also proved that for all c>0 there exists ε>0 such that for every comparability graph G with n>1 vertices, there is a pure pair A, B with |A|,|B|≥εn1−c; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c>0, and all ℓ1,ℓ2≥4/c+9, there exists ε>0 such that, if G is an (n>1)-vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2, then there is a pure pair A, B in G with |A|≥εn and |B|≥εn1−c. This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph. 

   more » « less