اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn Guptas Co-density Conjecture
115
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $G=(V,E)$ be a multigraph. The {em cover index} $xi(G)$ of $G$ is the greatest integer $k$ for which there is a coloring of $E$ with $k$ colors such that each vertex of $G$ is incident with at least one edge of each color. Let $delta(G)$ be the minimum degree of $G$ and let $Phi(G)$ be the {em co-density} of $G$, defined by [Phi(G)=min Big{frac{2|E^+(U)|}{|U|+1}:,, U subseteq V, ,, |U|ge 3 hskip 2mm {rm and hskip 2mm odd} Big},] where $E^+(U)$ is the set of all edges of $G$ with at least one end in $U$. It is easy to see that $xi(G) le min{delta(G), lfloor Phi(G) rfloor}$. In 1978 Gupta proposed the following co-density conjecture: Every multigraph $G$ satisfies $xi(G)ge min{delta(G)-1, , lfloor Phi(G) rfloor}$, which is the dual version of the Goldberg-Seymour conjecture on edge-colorings of multigraphs. In this note we prove that $xi(G)ge min{delta(G)-1, , lfloor Phi(G) rfloor}$ if $Phi(G)$ is not integral and $xi(G)ge min{delta(G)-2, , lfloor Phi(G) rfloor-1}$ otherwise. We also show that this co-density conjecture implies another conjecture concerning cover index made by Gupta in 1967.
قيم البحث
اقرأ أيضاً
Let $G$ be a $k$-connected graph on $n$ vertices. Hippchens Conjecture states that two longest paths in $G$ share at least $k$ vertices. Gutierrez recently proved the conjecture when $kleq 4$ or $kgeq frac{n-2}{3}$. We improve upon both results; name
ly, we show that two longest paths in $G$ share at least $k$ vertices when $k=5$ or $kgeq frac{n+2}{5}$. This completely resolves two conjectures of Gutierrez in the affirmative.
Karasev conjectured that for any set of $3k$ lines in general position in the plane, which is partitioned into $3$ color classes of equal size $k$, the set can be partitioned into $k$ colorful 3-subsets such that all the triangles formed by the subse
ts have a point in common. Although the general conjecture is false, we show that Karasevs conjecture is true for lines in convex position. We also discuss possible generalizations of this result.
In 1972, Erd{o}s - Faber - Lov{a}sz (EFL) conjectured that, if $textbf{H}$ is a linear hypergraph consisting of $n$ edges of cardinality $n$, then it is possible to color the vertices with $n$ colors so that no two vertices with the same color are in
the same edge. In 1978, Deza, Erd{o}s and Frankl had given an equivalent version of the same for graphs: Let $G= bigcup_{i=1}^{n} A_i$ denote a graph with $n$ complete graphs $A_1, A_2,$ $ dots , A_n$, each having exactly $n$ vertices and have the property that every pair of complete graphs has at most one common vertex, then the chromatic number of $G$ is $n$. The clique degree $d^K(v)$ of a vertex $v$ in $G$ is given by $d^K(v) = |{A_i: v in V(A_i), 1 leq i leq n}|$. In this paper we give a method for assigning colors to the graphs satisfying the hypothesis of the Erdos - Faber - Lovasz conjecture using intersection matrix of the cliques $A_i$s of $G$ and clique degrees of the vertices of $G$. Also, we give theoretical proof of the conjecture for some class of graphs. In particular we show that: 1. If $G$ is a graph satisfying the hypothesis of the Conjecture 1.2 and every $A_i$ ($1 leq i leq n$) has at most $sqrt{n}$ vertices of clique degree greater than 1, then $G$ is $n$-colorable. 2. If $G$ is a graph satisfying the hypothesis of the Conjecture 1.2 and every $A_i$ ($1 leq i leq n$) has at most $left lceil {frac{n+d-1}{d}} right rceil$ vertices of clique degree greater than or equal to $d$ ($2leq d leq n$), then $G$ is $n$-colorable.
Hadwigers conjecture is one of the most important and long-standing conjectures in graph theory. Reed and Seymour showed in 2004 that Hadwigers conjecture is true for line graphs. We investigate this conjecture on the closely related class of total g
raphs. The total graph of $G$, denoted by $T(G)$, is defined on the vertex set $V(G)sqcup E(G)$ with $c_1,c_2in V(G)sqcup E(G)$ adjacent whenever $c_1$ and $c_2$ are adjacent to or incident on each other in $G$. We first show that there exists a constant $C$ such that, if the connectivity of $G$ is at least $C$, then Hadwigers conjecture is true for $T(G)$. The total chromatic number $chi(G)$ of a graph $G$ is defined to be equal to the chromatic number of its total graph. That is, $chi(G)=chi(T(G))$. Another well-known conjecture in graph theory, the total coloring conjecture or TCC, states that for every graph $G$, $chi(G)leqDelta(G)+2$, where $Delta(G)$ is the maximum degree of $G$. We show that if a weaker version of the total coloring conjecture (weak TCC) namely, $chi(G)leqDelta(G)+3$, is true for a class of graphs $mathcal{F}$ that is closed under the operation of taking subgraphs, then Hadwigers conjecture is true for the class of total graphs of graphs in $mathcal{F}$. This motivated us to look for classes of graphs that satisfy weak TCC. It may be noted that a complete proof of TCC for even 4-colorable graphs (in fact even for planar graphs) has remained elusive even after decades of effort; but weak TCC can be proved easily for 4-colorable graphs. We noticed that in spite of the interest in studying $chi(G)$ in terms of $chi(G)$ right from the initial days, weak TCC is not proven to be true for $k$-colorable graphs even for $k=5$. In the second half of the paper, we make a contribution to the literature on total coloring by proving that $chi(G)leqDelta(G)+3$ for every 5-colorable graph $G$.
The extremal number $mathrm{ex}(n,F)$ of a graph $F$ is the maximum number of edges in an $n$-vertex graph not containing $F$ as a subgraph. A real number $r in [1,2]$ is realisable if there exists a graph $F$ with $mathrm{ex}(n , F) = Theta(n^r)$. S
everal decades ago, ErdH{o}s and Simonovits conjectured that every rational number in $[1,2]$ is realisable. Despite decades of effort, the only known realisable numbers are $0,1, frac{7}{5}, 2$, and the numbers of the form $1+frac{1}{m}$, $2-frac{1}{m}$, $2-frac{2}{m}$ for integers $m geq 1$. In particular, it is not even known whether the set of all realisable numbers contains a single limit point other than two numbers $1$ and $2$. In this paper, we make progress on the conjecture of ErdH{o}s and Simonovits. First, we show that $2 - frac{a}{b}$ is realisable for any integers $a,b geq 1$ with $b>a$ and $b equiv pm 1 ~({rm mod}:a)$. This includes all previously known ones, and gives infinitely many limit points $2-frac{1}{m}$ in the set of all realisable numbers as a consequence. Secondly, we propose a conjecture on subdivisions of bipartite graphs. Apart from being interesting on its own, we show that, somewhat surprisingly, this subdivision conjecture in fact implies that every rational number between 1 and 2 is realisable.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
