اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe chromatic number of finite type-graphs
165
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
By a finite type-graph we mean a graph whose set of vertices is the set of all $k$-subsets of $[n]={1,2,ldots, n}$ for some integers $nge kge 1$, and in which two such sets are adjacent if and only if they realise a certain order type specified in advance. Examples of such graphs have been investigated in a great variety of contexts in the literature with particular attention being paid to their chromatic number. In recent joint work with Tomasz {L}uczak, two of the authors embarked on a systematic study of the chromatic numbers of such type-graphs, formulated a general conjecture determining this number up to a multiplicative factor, and proved various results of this kind. In this article we fully prove this conjecture.
قيم البحث
اقرأ أيضاً
A signed graph is a pair $(G, sigma)$, where $G$ is a graph and $sigma: E(G) to {+, -}$ is a signature which assigns to each edge of $G$ a sign. Various notions of coloring of signed graphs have been studied. In this paper, we extend circular colorin
g of graphs to signed graphs. Given a signed graph $(G, sigma)$ a circular $r$-coloring of $(G, sigma)$ is an assignment $psi$ of points of a circle of circumference $r$ to the vertices of $G$ such that for every edge $e=uv$ of $G$, if $sigma(e)=+$, then $psi(u)$ and $psi(v)$ have distance at least $1$, and if $sigma(e)=-$, then $psi(v)$ and the antipodal of $psi(u)$ have distance at least $1$. The circular chromatic number $chi_c(G, sigma)$ of a signed graph $(G, sigma)$ is the infimum of those $r$ for which $(G, sigma)$ admits a circular $r$-coloring. For a graph $G$, we define the signed circular chromatic number of $G$ to be $max{chi_c(G, sigma): sigma text{ is a signature of $G$}}$. We study basic properties of circular coloring of signed graphs and develop tools for calculating $chi_c(G, sigma)$. We explore the relation between the circular chromatic number and the signed circular chromatic number of graphs, and present bounds for the signed circular chromatic number of some families of graphs. In particular, we determine the supremum of the signed circular chromatic number of $k$-chromatic graphs of large girth, of simple bipartite planar graphs, $d$-degenerate graphs, simple outerplanar graphs and series-parallel graphs. We construct a signed planar simple graph whose circular chromatic number is $4+frac{2}{3}$. This is based and improves on a signed graph built by Kardos and Narboni as a counterexample to a conjecture of M{a}v{c}ajov{a}, Raspaud, and v{S}koviera.
Let Q(n,c) denote the minimum clique size an n-vertex graph can have if its chromatic number is c. Using Ramsey graphs we give an exact, albeit implicit, formula for the case c is at least (n+3)/2.
Let $G$ be a simple graph with maximum degree $Delta(G)$ and chromatic index $chi(G)$. A classic result of Vizing indicates that either $chi(G )=Delta(G)$ or $chi(G )=Delta(G)+1$. The graph $G$ is called $Delta$-critical if $G$ is connected, $chi(G )
=Delta(G)+1$ and for any $ein E(G)$, $chi(G-e)=Delta(G)$. Let $G$ be an $n$-vertex $Delta$-critical graph. Vizing conjectured that $alpha(G)$, the independence number of $G$, is at most $frac{n}{2}$. The current best result on this conjecture, shown by Woodall, is that $alpha(G)<frac{3n}{5}$. We show that for any given $varepsilonin (0,1)$, there exist positive constants $d_0(varepsilon)$ and $D_0(varepsilon)$ such that if $G$ is an $n$-vertex $Delta$-critical graph with minimum degree at least $d_0$ and maximum degree at least $D_0$, then $alpha(G)<(frac{{1}}{2}+varepsilon)n$. In particular, we show that if $G$ is an $n$-vertex $Delta$-critical graph with minimum degree at least $d$ and $Delta(G)ge (d+2)^{5d+10}$, then [ alpha(G) < left. begin{cases} frac{7n}{12}, & text{if $d= 3$; } frac{4n}{7}, & text{if $d= 4$; } frac{d+2+sqrt[3]{(d-1)d}}{2d+4+sqrt[3]{(d-1)d}}n<frac{4n}{7}, & text{if $dge 19$. } end{cases} right. ]
For a simple graph $G$, let $chi_f(G)$ be the fractional chromatic number of $G$. In this paper, we aim to establish upper bounds on $chi_f(G)$ for those graphs $G$ with restrictions on the clique number. Namely, we prove that for $Delta geq 4$, if $
G$ has maximum degree at most $Delta$ and is $K_{Delta}$-free, then $chi_f(G) leq Delta-tfrac{1}{8}$ unless $G= C^2_8$ or $G = C_5boxtimes K_2$. This im proves the result in [King, Lu, and Peng, SIAM J. Discrete Math., 26(2) (2012), pp. 452-471] for $Delta geq 4$ and the result in [Katherine and King, SIAM J.Discrete Math., 27(2) (2013), pp. 1184-1208] for $Delta in {6,7,8}$.
Assume $n, m$ are positive integers and $G$ is a graph. Let $P_{n,m}$ be the graph obtained from the path with vertices ${-m, -(m-1), ldots, 0, ldots, n}$ by adding a loop at vertex $ 0$. The double cone $Delta_{n,m}(G)$ over a graph $G$ is obtained
from the direct product $G times P_{n,m}$ by identifying $V(G) times {n}$ into a single vertex $(star, n)$, identifying $V(G) times {-m}$ into a single vertex $(star, -m)$, and adding an edge connecting $(star, -m)$ and $(star, n)$. This paper determines the fractional chromatic number of $Delta_{n,m}(G)$. In particular, if $n < m$ or $n=m$ is even, then $chi_f(Delta_{n,m}(G)) = chi_f(Delta_n(G))$, where $Delta_n(G)$ is the $n$th cone over $G$. If $n=m$ is odd, then $chi_f(Delta_{n,m}(G)) > chi_f(Delta_n(G))$. The chromatic number of $Delta_{n,m}(G)$ is also discussed.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
