ترغب بنشر مسار تعليمي؟ اضغط هنا

Local colourings and monochromatic partitions in complete bipartite graphs

117   0   0.0 ( 0 )
 نشر من قبل Richard Lang
 تاريخ النشر 2015
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

We show that for any $2$-local colouring of the edges of the balanced complete bipartite graph $K_{n,n}$, its vertices can be covered with at most~$3$ disjoint monochromatic paths. And, we can cover almost all vertices of any complete or balanced complete bipartite $r$-locally coloured graph with $O(r^2)$ disjoint monochromatic cycles. We also determine the $2$-local bipartite Ramsey number of a path almost exactly: Every $2$-local colouring of the edges of $K_{n,n}$ contains a monochromatic path on $n$ vertices.



قيم البحث

اقرأ أيضاً

123 - Richard Lang , Allan Lo 2018
ErdH{o}s, Gyarfas and Pyber showed that every $r$-edge-coloured complete graph $K_n$ can be covered by $25 r^2 log r$ vertex-disjoint monochromatic cycles (independent of $n$). Here, we extend their result to the setting of binomial random graphs. Th at is, we show that if $p = p(n) = Omega(n^{-1/(2r)})$, then with high probability any $r$-edge-coloured $G(n,p)$ can be covered by at most $1000 r^4 log r $ vertex-disjoint monochromatic cycles. This answers a question of Korandi, Mousset, Nenadov, v{S}kori{c} and Sudakov.
A set of vertices X of a graph G is convex if it contains all vertices on shortest paths between vertices of X. We prove that for fixed p, all partitions of the vertex set of a bipartite graph into p convex sets can be found in polynomial time.
253 - Xueliang Li , Fengxia Liu 2008
The monochromatic tree partition number of an $r$-edge-colored graph $G$, denoted by $t_r(G)$, is the minimum integer $k$ such that whenever the edges of $G$ are colored with $r$ colors, the vertices of $G$ can be covered by at most $k$ vertex-disjoi nt monochromatic trees. In general, to determine this number is very difficult. For 2-edge-colored complete multipartite graph, Kaneko, Kano, and Suzuki gave the exact value of $t_2(K(n_1,n_2,...,n_k))$. In this paper, we prove that if $ngeq 3$, and K(n,n) is 3-edge-colored such that every vertex has color degree 3, then $t_3(K(n,n))=3.$
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 wheels, complete bipartite graphs and complete graphs.
Let $mathrm{rex}(n, F)$ denote the maximum number of edges in an $n$-vertex graph that is regular and does not contain $F$ as a subgraph. We give lower bounds on $mathrm{rex}(n, F)$, that are best possible up to a constant factor, when $F$ is one of $C_4$, $K_{2,t}$, $K_{3,3}$ or $K_{s,t}$ when $t>s!$.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا