اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدChromatic numbers for the hyperbolic plane and discrete analogs
65
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We study colorings of the hyperbolic plane, analogously to the Hadwiger-Nelson problem for the Euclidean plane. The idea is to color points using the minimum number of colors such that no two points at distance exactly $d$ are of the same color. The problem depends on $d$ and, following a strategy of Kloeckner, we show linear upper bounds on the necessary number of colors. In parallel, we study the same problem on $q$-regular trees and show analogous results. For both settings, we also consider a variant which consists in replacing $d$ with an interval of distances.
قيم البحث
اقرأ أيضاً
Consider the graph $mathbb{H}(d)$ whose vertex set is the hyperbolic plane, where two points are connected with an edge when their distance is equal to some $d>0$. Asking for the chromatic number of this graph is the hyperbolic analogue to the famous
Hadwiger-Nelson problem about colouring the points of the Euclidean plane so that points at distance $1$ receive different colours. As in the Euclidean case, one can lower bound the chromatic number of $mathbb{H}(d)$ by $4$ for all $d$. Using spectral methods, we prove that if the colour classes are measurable, then at least $6$ colours are are needed to properly colour $mathbb{H}(d)$ when $d$ is sufficiently large.
A semi-regular tiling of the hyperbolic plane is a tessellation by regular geodesic polygons with the property that each vertex has the same vertex-type, which is a cyclic tuple of integers that determine the number of sides of the polygons surroundi
ng the vertex. We determine combinatorial criteria for the existence, and uniqueness, of a semi-regular tiling with a given vertex-type, and pose some open questions.
For graph $G$ and integers $a_1 ge cdots ge a_r ge 2$, we write $G rightarrow (a_1 ,cdots ,a_r)^v$ if and only if for every $r$-coloring of the vertex set $V(G)$ there exists a monochromatic $K_{a_i}$ in $G$ for some color $i in {1, cdots, r}$. The v
ertex Folkman number $F_v(a_1 ,cdots ,a_r; s)$ is defined as the smallest integer $n$ for which there exists a $K_s$-free graph $G$ of order $n$ such that $G rightarrow (a_1 ,cdots ,a_r)^v$. It is well known that if $G rightarrow (a_1 ,cdots ,a_r)^v$ then $chi(G) geq m$, where $m = 1+ sum_{i=1}^r (a_i - 1)$. In this paper we study such Folkman graphs $G$ with chromatic number $chi(G)=m$, which leads to a new concept of chromatic Folkman numbers. We prove constructively some existential results, among others that for all $r,s ge 2$ there exist $K_{s+1}$-free graphs $G$ such that $G rightarrow (s,cdots_r,s)^v$ and $G$ has the smallest possible chromatic number $r(s-1)+1$ for this $r$-color arrowing to hold. We also conjecture that, in some cases, our construction is the best possible, in particular that for every $s ge 2$ there exists a $K_{s+1}$-free graph $G$ on $F_v(s,s; s+1)$ vertices with $chi(G)=2s-1$ such that $G rightarrow (s,s)^v$.
The total dominator total coloring of a graph is a total coloring of the graph such that each object of the graph is adjacent or incident to every object of some color class. The minimum namber of the color classes of a total dominator total coloring
of a graph is called the total dominator total chromatic number of the graph. Here, we will find the total dominator chromatic numbers of cycles and paths.
Let $G=(V(G), E(G))$ be a multigraph with maximum degree $Delta(G)$, chromatic index $chi(G)$ and total chromatic number $chi(G)$. The Total Coloring conjecture proposed by Behzad and Vizing, independently, states that $chi(G)leq Delta(G)+mu(G) +1$ f
or a multigraph $G$, where $mu(G)$ is the multiplicity of $G$. Moreover, Goldberg conjectured that $chi(G)=chi(G)$ if $chi(G)geq Delta(G)+3$ and noticed the conjecture holds when $G$ is an edge-chromatic critical graph. By assuming the Goldberg-Seymour conjecture, we show that $chi(G)=chi(G)$ if $chi(G)geq max{ Delta(G)+2, |V(G)|+1}$ in this note. Consequently, $chi(G) = chi(G)$ if $chi(G) ge Delta(G) +2$ and $G$ has a spanning edge-chromatic critical subgraph.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
