اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدBipartite independence number and balanced coloring
372
0
0.0
(
0
)
تأليف
Debsoumya Chakraborti
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
In this paper, we establish a couple of results on extremal problems in bipartite graphs. Firstly, we show that every sufficiently large bipartite graph with average degree $Delta$ and with $n$ vertices on each side has a balanced independent set containing $(1-epsilon) frac{log Delta}{Delta} n$ vertices from each side for small $epsilon > 0$. Secondly, we prove that the vertex set of every sufficiently large balanced bipartite graph with maximum degree at most $Delta$ can be partitioned into $(1+epsilon)frac{Delta}{log Delta}$ balanced independent sets. Both of these results are algorithmic and best possible up to a factor of 2, which might be hard to improve as evidenced by the phenomenon known as `algorithmic barrier in the literature. The first result improves a recent theorem of Axenovich, Sereni, Snyder, and Weber in a slightly more general setting. The second result improves a theorem of Feige and Kogan about coloring balanced bipartite graphs.
قيم البحث
اقرأ أيضاً
The analogue of Hadwigers conjecture for the immersion order states that every graph $G$ contains $K_{chi (G)}$ as an immersion. If true, it would imply that every graph with $n$ vertices and independence number $alpha$ contains $K_{lceil frac nalpha
rceil}$ as an immersion. The best currently known bound for this conjecture is due to Gauthier, Le and Wollan, who recently proved that every graph $G$ contains an immersion of a clique on $bigllceil frac{chi (G)-4}{3.54}bigrrceil$ vertices. Their result implies that every $n$-vertex graph with independence number $alpha$ contains an immersion of a clique on $bigllceil frac{n}{3.54alpha}-1.13bigrrceil$ vertices. We improve on this result for all $alphage 3$, by showing that every $n$-vertex graph with independence number $alphage 3$ contains an immersion of a clique on $bigllfloor frac {n}{2.25 alpha - f(alpha)} bigrrfloor - 1$ vertices, where $f$ is a nonnegative function.
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 dom
inator coloring. In this article, we study the total dominator coloring on middle graphs by giving several bounds for the case of general graphs and trees. Moreover, we calculate explicitely the total dominator chromatic number of the middle graph of several known families of graphs.
Let $G=(V,E)$ be a graph and $n$ a positive integer. Let $I_n(G)$ be the abstract simplicial complex whose simplices are the subsets of $V$ that do not contain an independent set of size $n$ in $G$. We study the collapsibility numbers of the complexe
s $I_n(G)$ for various classes of graphs, focusing on the class of graphs with maximum degree bounded by $Delta$. As an application, we obtain the following result: Let $G$ be a claw-free graph with maximum degree at most $Delta$. Then, every collection of $leftlfloorleft(frac{Delta}{2}+1right)(n-1)rightrfloor+1$ independent sets in $G$ has a rainbow independent set of size $n$.
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. ]
We study the possible values of the matching number among all trees with a given degree sequence as well as all bipartite graphs with a given bipartite degree sequence. For tree degree sequences, we obtain closed formulas for the possible values. For
bipartite degree sequences, we show the existence of realizations with a restricted structure, which allows to derive an analogue of the Gale-Ryser Theorem characterizing bipartite degree sequences. More precisely, we show that a bipartite degree sequence has a realization with a certain matching number if and only if a cubic number of inequalities similar to those in the Gale-Ryser Theorem are satisfied. For tree degree sequences as well as for bipartite degree sequences, the possible values of the matching number form intervals.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
