|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
On Gupta's Co-density Conjecture | | Yan Cao
; Guantao Chen
; Guoli Ding
; Guangming Jing
; Wenan Zang
; | | Date: |
15 Jun 2019 | | Abstract: | 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 {
m
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)
floor}$. In 1978 Gupta proposed the
following co-density conjecture: Every multigraph $G$ satisfies $xi(G)ge
min{delta(G)-1, , lfloor Phi(G)
floor}$, 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)
floor}$ if
$Phi(G)$ is not integral and $xi(G)ge min{delta(G)-2, , lfloor Phi(G)
floor-1}$ otherwise. We also show that this co-density conjecture implies
another conjecture concerning cover index made by Gupta in 1967. | | Source: | arXiv, 1906.6458 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER