اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدColoring connections with counting mountain-valley assignments
48
0
0.0
(
0
)
تأليف
Thomas C. Hull
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We survey more recent attempts at enumerating the number of mountain-valley assignments that allow a given crease pattern to locally fold flat. In particular, we solve this problem for square twist tessellations and generalize the method used to a broader family of crease patterns. We also describe the more difficult case of the Miura-ori and a recently-discovered bijection with 3-vertex colorings of grid graphs.
قيم البحث
اقرأ أيضاً
It is proved that triangle-free intersection graphs of $n$ L-shapes in the plane have chromatic number $O(loglog n)$. This improves the previous bound of $O(log n)$ (McGuinness, 1996) and matches the known lower bound construction (Pawlik et al., 2013).
Origami, where two-dimensional sheets are folded into complex structures, is proving to be rich with combinatorial and geometric structure, most of which remains to be fully understood. In this paper we consider emph{flat origami}, where the sheet of
material is folded into a two-dimensional object, and consider the mountain (convex) and valley (concave) creases made by such foldings, called a emph{MV assignment} of the crease pattern. We establish a method to, given a flat-foldable crease pattern $C$ under certain conditions, create a planar graph $C^*$ whose 3-colorings are in one-to-one correspondence with the locally-valid MV assignments of $C$. This reduces the general, unsolved problem of enumerating locally-valid MV assignments to the enumeration of 3-colorings of graphs.
Let $G$ be a simple graph with maximum degree $Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>Delta(G)lfloor |V(H)|/2 rfloor$. Chetwynd and Hilton in 1985 conjectured that a graph $G$ with $Delta(G)>|V(G)|/3$ has chromatic index $Delta(G)$ i
f and only if $G$ contains no overfull subgraph. The 1-factorization conjecture is a special case of this overfull conjecture, which states that for even $n$, every regular $n$-vertex graph with degree at least about $n/2$ has a 1-factorization and was confirmed for large graphs in 2014. Supporting the overfull conjecture as well as generalizing the 1-factorization conjecture in an asymptotic way, in this paper, we show that for any given $0<varepsilon <1$, there exists a positive integer $n_0$ such that the following statement holds: if $G$ is a graph on $2nge n_0$ vertices with minimum degree at least $(1+varepsilon)n$, then $G$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph.
If the vertices of a graph $G$ are colored with $k$ colors such that no adjacent vertices receive the same color and the sizes of any two color classes differ by at most one, then $G$ is said to be equitably $k$-colorable. Let $|G|$ denote the number
of vertices of $G$ and $Delta=Delta(G)$ the maximum degree of a vertex in $G$. We prove that a graph $G$ of order at least 6 is equitably $Delta$-colorable if $G$ satisfies $(|G|+1)/3 leq Delta < |G|/2$ and none of its components is a $K_{Delta +1}$.
Motivated by the ErdH{o}s-Faber-Lov{a}sz (EFL) conjecture for hypergraphs, we consider the list edge coloring of linear hypergraphs. We show that if the hyper-edge sizes are bounded between $i$ and $C_{i,epsilon} sqrt{n}$ inclusive, then there is a l
ist edge coloring using $(1 + epsilon) frac{n}{i - 1}$ colors. The dependence on $n$ in the upper bound is optimal (up to the value of $C_{i,epsilon}$).
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
