اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدFive-coloring graphs on the Klein bottle
278
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We exhibit an explicit list of nine graphs such that a graph drawn in the Klein bottle is 5-colorable if and only if it has no subgraph isomorphic to a member of the list.
قيم البحث
اقرأ أيضاً
The star chromatic index of a multigraph $G$, denoted $chi_{st}(G)$, is the minimum number of colors needed to properly color the edges of $G$ such that no path or cycle of length four is bicolored. We survey the results of determining the star chrom
atic index, present the interesting proofs and techniques, and collect many open problems and conjectures.
For a given graph $G$, the least integer $kgeq 2$ such that for every Abelian group $mathcal{G}$ of order $k$ there exists a proper edge labeling $f:E(G)rightarrow mathcal{G}$ so that $sum_{xin N(u)}f(xu) eq sum_{xin N(v)}f(xv)$ for each edge $uvin E
(G)$ is called the textit{group twin chromatic index} of $G$ and denoted by $chi_g(G)$. This graph invariant is related to a few well-known problems in the field of neighbor distinguishing graph colorings. We conjecture that $chi_g(G)leq Delta(G)+3$ for all graphs without isolated edges, where $Delta(G)$ is the maximum degree of $G$, and provide an infinite family of connected graph (trees) for which the equality holds. We prove that this conjecture is valid for all trees, and then apply this result as the base case for proving a general upper bound for all graphs $G$ without isolated edges: $chi_g(G)leq 2(Delta(G)+{rm col}(G))-5$, where ${rm col}(G)$ denotes the coloring number of $G$. This improves the best known upper bound known previously only for the case of cyclic groups $mathbb{Z}_k$.
In this paper, based on the contributions of Tucker (1983) and Seb{H{o}} (1992), we generalize the concept of a sequential coloring of a graph to a framework in which the algorithm may use a coloring rule-base obtained from suitable forcing structure
s. In this regard, we introduce the {it weak} and {it strong sequential defining numbers} for such colorings and as the main results, after proving some basic properties, we show that these two parameters are intrinsically different and their spectra are nontrivial. Also, we consider the natural problems related to the complexity of computing such parameters and we show that in a variety of cases these problems are ${bf NP}$-complete. We conjecture that this result does not depend on the rule-base for all nontrivial cases.
The textit{$k$-weak-dynamic number} of a graph $G$ is the smallest number of colors we need to color the vertices of $G$ in such a way that each vertex $v$ of degree $d(v)$ sees at least $rm{min}{k,d(v)}$ colors on its neighborhood. We use reducible
configurations and list coloring of graphs to prove that all planar graphs have 3-weak-dynamic number at most 6.
A total dominator coloring of a graph $G$ is a proper coloring of $G$ in which each vertex of the graph is adjacent to every vertex of some color class. The total dominator chromatic number of a graph is the minimum number of color classes in a total
dominator coloring of it. Here, we study the total dominator coloring on central graphs by giving some tight bounds for the total dominator chromatic number of the central of a graph, join of two graphs and Nordhaus-Gaddum-like relations. Also we will calculate the total dominator chromatic number of the central of a path, a cycle, a wheel, a complete graph and a complete multipartite graph.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
