اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPrecoloring extension involving pairs of vertices of small distance
76
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper, we consider coloring of graphs under the assumption that some vertices are already colored. Let $G$ be an $r$-colorable graph and let $Psubset V(G)$. Albertson [J. Combin. Theory Ser. B textbf{73} (1998), 189--194] has proved that if every pair of vertices in $P$ have distance at least four, then every $(r+1)$-coloring of $G[P]$ can be extended to an $(r+1)$-coloring of $G$, where $G[P]$ is the subgraph of $G$ induced by $P$. In this paper, we allow $P$ to have pairs of vertices of distance at most three, and investigate how the number of such pairs affects the number of colors we need to extend the coloring of $G[P]$. We also study the effect of pairs of vertices of distance at most two, and extend the result by Albertson and Moore [J. Combin. Theory Ser. B textbf{77} (1999) 83--95].
قيم البحث
اقرأ أيضاً
Given any graph $H$, a graph $G$ is said to be $q$-Ramsey for $H$ if every coloring of the edges of $G$ with $q$ colors yields a monochromatic subgraph isomorphic to $H$. Further, such a graph $G$ is said to be minimal $q$-Ramsey for $H$ if additiona
lly no proper subgraph $G$ of $G$ is $q$-Ramsey for $H$. In 1976, Burr, ErdH{o}s, and Lovasz initiated the study of the parameter $s_q(H)$, defined as the smallest minimum degree among all minimal $q$-Ramsey graphs for $H$. In this paper, we consider the problem of determining how many vertices of degree $s_q(H)$ a minimal $q$-Ramsey graph for $H$ can contain. Specifically, we seek to identify graphs for which a minimal $q$-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property $s_q$-abundant. Among other results, we prove that every cycle is $s_q$-abundant for any integer $qgeq 2$. We also discuss the cases when $H$ is a clique or a clique with a pendant edge, extending previous results of Burr et al. and Fox et al. To prove our results and construct suitable minimal Ramsey graphs, we develop certain new gadget graphs, called pattern gadgets, which generalize and extend earlier constructions that have proven useful in the study of minimal Ramsey graphs. These new gadgets might be of independent interest.
Hakimi and Schmeichel determined a sharp lower bound for the number of cycles of length 4 in a maximal planar graph with $n$ vertices, $ngeq 5$. It has been shown that the bound is sharp for $n = 5,12$ and $ngeq 14$ vertices. However, it was only con
jectured by the authors about the minimum number of cycles of length 4 for maximal planar graphs with the remaining small vertex numbers. In this note we confirm their conjecture.
It is an open question whether the linear extension complexity of the Cartesian product of two polytopes P, Q is the sum of the extension complexities of P and Q. We give an affirmative answer to this question for the case that one of the two polytopes is a pyramid.
The main contribution of this paper is a new column-by-column method for the decomposition of generating functions of convex polyominoes suitable for enumeration with respect to various statistics including but not limited to interior vertices, bound
ary vertices of certain degrees, and outer site perimeter. Using this decomposition, among other things, we show that A) the average number of interior vertices over all convex polyominoes of perimeter $2n$ is asymptotic to $frac{n^2}{12}+frac{nsqrt{n}}{3sqrt{pi}} -frac{(21pi-16)n}{12pi}.$ B) the average number of boundary vertices with degree two over all convex polyominoes of perimeter $2n$ is asymptotic to $frac{n+6}{2}+frac{1}{sqrt{pi n}}+frac{(16-7pi)}{4pi n}.$ Additionally, we obtain an explicit generating function counting the number of convex polyominoes with $n$ boundary vertices of degrees at most three and show that this number is asymptotic to $ frac{n+1}{40}left(frac{3+sqrt{5}}{2}right)^{n-3} +frac{sqrt[4]{5}(2-sqrt{5})}{80sqrt{pi n}}left(frac{3+sqrt{5}}{2}right)^{n-2}. $ Moreover, we show that the expected number of the boundary vertices of degree four over all convex polyominoes with $n$ vertices of degrees at most three is asymptotically $ frac{n}{sqrt{5}}-frac{sqrt[4]{125}(sqrt{5}-1)sqrt{n}}{10sqrt{pi}}. $ C) the number of convex polyominoes with the outer-site perimeter $n$ is asymptotic to $frac{3(sqrt{5}-1)}{20sqrt{pi n}sqrt[4]{5}}left(frac{3+sqrt{5}}{2}right)^n,$ and show the expected number of the outer-site perimeter over all convex polyominoes with perimeter $2n$ is asymptotic to $frac{25n}{16}+frac{sqrt{n}}{4sqrt{pi}}+frac{1}{8}.$ Lastly, we prove that the expected perimeter over all convex polyominoes with the outer-site perimeter $n$ is asymptotic to $sqrt[4]{5}n$.
We provide a simple characterization of simplicial complexes on few vertices that embed into the $d$-sphere. Namely, a simplicial complex on $d+3$ vertices embeds into the $d$-sphere if and only if its non-faces do not form an intersecting family. As
immediate consequences, we recover the classical van Kampen--Flores theorem and provide a topological extension of the ErdH os--Ko--Rado theorem. By analogy with Farys theorem for planar graphs, we show in addition that such complexes satisfy the rigidity property that continuous and linear embeddability are equivalent.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
