اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدChromatic index of dense quasirandom graphs
76
0
0.0
(
0
)
تأليف
Songling Shan
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $G$ be a simple graph with maximum degree $Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>Delta(G)lfloor |V(H)|/2 rfloor$. Chetwynd and Hilton in 1985 conjectured that a graph $G$ on $n$ vertices with $Delta(G)>n/3$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph. Glock, K{u}hn and Osthus in 2016 showed that the conjecture is true for dense quasirandom graphs with even order, and they conjectured that the same should hold for such graphs with odd order. In this paper, we show that the conjecture of Glock, K{u}hn and Osthus is affirmative.
قيم البحث
اقرأ أيضاً
A strong edge colouring of a graph is an assignment of colours to the edges of the graph such that for every colour, the set of edges that are given that colour form an induced matching in the graph. The strong chromatic index of a graph $G$, denoted
by $chi_s(G)$, is the minimum number of colours needed in any strong edge colouring of $G$. A graph is said to be emph{chordless} if there is no cycle in the graph that has a chord. Faudree, Gyarfas, Schelp and Tuza~[The Strong Chromatic Index of Graphs, Ars Combin., 29B (1990), pp.~205--211] considered a particular subclass of chordless graphs, namely the class of graphs in which all the cycle lengths are multiples of four, and asked whether the strong chromatic index of these graphs can be bounded by a linear function of the maximum degree. Chang and Narayanan~[Strong Chromatic Index of 2-degenerate Graphs, J. Graph Theory, 73(2) (2013), pp.~119--126] answered this question in the affirmative by proving that if $G$ is a chordless graph with maximum degree $Delta$, then $chi_s(G) leq 8Delta -6$. We improve this result by showing that for every chordless graph $G$ with maximum degree $Delta$, $chi_s(G)leq 3Delta$. This bound is tight up to to an additive constant.
A strong $k$-edge-coloring of a graph G is an edge-coloring with $k$ colors in which every color class is an induced matching. The strong chromatic index of $G$, denoted by $chi_{s}(G)$, is the minimum $k$ for which $G$ has a strong $k$-edge-coloring
. In 1985, ErdH{o}s and Nev{s}etv{r}il conjectured that $chi_{s}(G)leqfrac{5}{4}Delta(G)^2$, where $Delta(G)$ is the maximum degree of $G$. When $G$ is a graph with maximum degree at most 3, the conjecture was verified independently by Andersen and Hor{a}k, Qing, and Trotter. In this paper, we consider the list version of strong edge-coloring. In particular, we show that every subcubic graph has strong list-chromatic index at most 11 and every planar subcubic graph has strong list-chromatic index at most 10.
In this short note we observe that recent results of Abert and Hubai and of Csikvari and Frenkel about Benjamini--Schramm continuity of the holomorphic moments of the roots of the chromatic polynomial extend to the theory of dense graph sequences. We
offer a number of problems and conjectures motivated by this observation.
The strong chromatic index of a graph $G$, denoted $chi_s(G)$, is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted $chi_{s,ell}(G)$, is the lea
st integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors. We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with $operatorname{girth}(G) geq 41$ then $chi_{s,ell}(G) leq 5$, answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and $operatorname{girth}(G) geq 30$, then $chi_s(G) leq 5$, improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $operatorname{girth}(G) geq 28$, then $chi_s(G) leq 7$, improving a more general bound of Wang and Zhao from [Odd graphs and its application on the strong edge coloring, arXiv:1412.8358] in this case.
Let $chi_k(G)$ denote the minimum number of colors needed to color the edges of a graph $G$ in a way that the subgraph spanned by the edges of each color has all degrees congruent to $1 pmod k$. Scott [{em Discrete Math. 175}, 1-3 (1997), 289--291] p
roved that $chi_k(G)leq5k^2log k$, and thus settled a question of Pyber [{em Sets, graphs and numbers} (1992), pp. 583--610], who had asked whether $chi_k(G)$ can be bounded solely as a function of $k$. We prove that $chi_k(G)=O(k)$, answering affirmatively a question of Scott.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
