Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSymmetric colorings of polypolyhedra
45
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Polypolyhedra (after R. Lang) are compounds of edge-transitive 1-skeleta. There are 54 topologically different polypolyhedra, and each has icosidodecahedral, cuboctahedral, or tetrahedral symmetry, all are realizable as modular origami models with one module per skeleton edge. Consider a coloring in which each edge of a given component receives a different color, and where the coloring (up to global color permutation) is invariant under the polypolyhedrons symmetry group. On the Five Intersecting Tetrahedra, the edges of each color form visual bands on the model, and correspond to matchings on the dodecahedron graph. We count the number of such colorings and give three proofs. For each of the non-polygon-component polypolyhedra, there is a corresponding matching coloring, and we count the number of these matching colorings. For some of the non-polygon-component polypolyhedra, there is a corresponding visual-band coloring, and we count the number of these band colorings.
rate research
Read More
In a recent paper by the same authors, we constructed a stationary 1-dependent 4-coloring of the integers that is invariant under permutations of the colors. This was the first stationary k-dependent q-coloring for any k and q. When the analogous construction is carried out for q>4 colors, the resulting process is not k-dependent for any k. We construct here a process that is symmetric in the colors and 1-dependent for every q>=4. The construction uses a recursion involving Chebyshev polynomials evaluated at $sqrt{q}/2$.
We develop a combinatorial rigidity theory for symmetric bar-joint frameworks in a general finite dimensional normed space. In the case of rotational symmetry, matroidal Maxwell-type sparsity counts are identified for a large class of $d$-dimensional normed spaces (including all $ell^p$ spaces with $p ot=2$). Complete combinatorial characterisations are obtained for half-turn rotation in the $ell^1$ and $ell^infty$-plane. As a key tool, a new Henneberg-type inductive construction is developed for the matroidal class of $(2,2,0)$-gain-tight graphs.
An edge-coloring of a graph $G$ with colors $1,2,ldots,t$ is an interval $t$-coloring if all colors are used, and the colors of edges incident to each vertex of $G$ are distinct and form an interval of integers. A graph $G$ is interval colorable if it has an interval $t$-coloring for some positive integer $t$. For an interval colorable graph $G$, $W(G)$ denotes the greatest value of $t$ for which $G$ has an interval $t$-coloring. It is known that the complete graph is interval colorable if and only if the number of its vertices is even. However, the exact value of $W(K_{2n})$ is known only for $n leq 4$. The second author showed that if $n = p2^q$, where $p$ is odd and $q$ is nonnegative, then $W(K_{2n}) geq 4n-2-p-q$. Later, he conjectured that if $n in mathbb{N}$, then $W(K_{2n}) = 4n - 2 - leftlfloorlog_2{n}rightrfloor - left | n_2 right |$, where $left | n_2 right |$ is the number of $1$s in the binary representation of $n$. In this paper we introduce a new technique to construct interval colorings of complete graphs based on their 1-factorizations, which is used to disprove the conjecture, improve lower and upper bounds on $W(K_{2n})$ and determine its exact values for $n leq 12$.
This paper is concerned with symmetric $1$-dependent colorings of the $d$-ray star graph $mathscr{S}^d$ for each $d ge 2$. We compute the critical point of the $1$-dependent hard-core processes on $mathscr{S}^d$, which gives a lower bound for the number of colors needed for a $1$-dependent coloring of $mathscr{S}^d$. We provide an explicit construction of a $1$-dependent $q$-coloring for any $q ge 5$ of the infinite subgraph $mathscr{S}^3_{(1,1,infty)}$, which is symmetric in the colors and whose restriction to any copy of $mathbb{Z}$ is some symmetric $1$-dependent $q$-coloring of $mathbb{Z}$. We also prove that there is no such coloring of $mathscr{S}^3_{(1,1,infty)}$ with $q = 4$ colors. A list of open problems are presented.
A $k$-proper edge-coloring of a graph G is called adjacent vertex-distinguishing if any two adjacent vertices are distinguished by the set of colors appearing in the edges incident to each vertex. The smallest value $k$ for which $G$ admits such coloring is denoted by $chi_a(G)$. We prove that $chi_a(G) = 2R + 1$ for most circulant graphs $C_n([1, R])$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
