File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Approximating the chromatic index of multigraphs

TitleApproximating the chromatic index of multigraphs
Authors
KeywordsChromatic index
Edge coloring
Fractional chromatic index
Multigraph
Issue Date2011
PublisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905
Citation
Journal Of Combinatorial Optimization, 2011, v. 21 n. 2, p. 219-246 How to Cite?
AbstractIt is well known that if G is a multigraph then χ′(G) ≥χ′ *(G):=max{Δ(G),Γ(G)}, where χ′(G) is the chromatic index of G, χ′ *(G) is the fractional chromatic index of G, Δ(G) is the maximum degree of G, and Γ(G)=max{2|E(G[U])|/(|U|-1):U ⊇ V(G),|U|≥3,|U| is odd}. The conjecture that χ′(G)≤max{Δ(G)+1,Γ(G) was made independently by Goldberg (Discret. Anal. 23:3-7, 1973), Anderson (Math. Scand. 40:161-175, 1977), and Seymour (Proc. Lond. Math. Soc. 38:423-460, 1979). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′(G)≤χ′ *(G)+c χ′ *(G) when χ′ *(G)>D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′(G)>⌊(11Δ(G)+8)/10⌋ and Scheide recently improved this bound to χ′(G)>⌊(15Δ(G)+12)/14⌋. We prove this conjecture for multigraphs G with χ′(G)> ⌊ Δ(G)+ Δ(G)/2 ⌋, improving the above mentioned results. As a consequence, for multigraphs G with χ(G)>Delta(G)+sqrt Δ(G)/2} the answer to a 1964 problem of Vizing is in the affirmative. © 2009 Springer Science+Business Media, LLC.
Persistent Identifierhttp://hdl.handle.net/10722/137323
ISSN
2015 Impact Factor: 1.08
2015 SCImago Journal Rankings: 1.093
ISI Accession Number ID
Funding AgencyGrant Number
NSF
NSA
NSFC10628102
Research Grants Council of Hong Kong
Funding Information:

G. Chen is partially supported by NSF.

References

 

DC FieldValueLanguage
dc.contributor.authorChen, Gen_HK
dc.contributor.authorYu, Xen_HK
dc.contributor.authorZang, Wen_HK
dc.date.accessioned2011-08-26T14:23:16Z-
dc.date.available2011-08-26T14:23:16Z-
dc.date.issued2011en_HK
dc.identifier.citationJournal Of Combinatorial Optimization, 2011, v. 21 n. 2, p. 219-246en_HK
dc.identifier.issn1382-6905en_HK
dc.identifier.urihttp://hdl.handle.net/10722/137323-
dc.description.abstractIt is well known that if G is a multigraph then χ′(G) ≥χ′ *(G):=max{Δ(G),Γ(G)}, where χ′(G) is the chromatic index of G, χ′ *(G) is the fractional chromatic index of G, Δ(G) is the maximum degree of G, and Γ(G)=max{2|E(G[U])|/(|U|-1):U ⊇ V(G),|U|≥3,|U| is odd}. The conjecture that χ′(G)≤max{Δ(G)+1,Γ(G) was made independently by Goldberg (Discret. Anal. 23:3-7, 1973), Anderson (Math. Scand. 40:161-175, 1977), and Seymour (Proc. Lond. Math. Soc. 38:423-460, 1979). Using a probabilistic argument Kahn showed that for any c>0 there exists D>0 such that χ′(G)≤χ′ *(G)+c χ′ *(G) when χ′ *(G)>D. Nishizeki and Kashiwagi proved this conjecture for multigraphs G with χ′(G)>⌊(11Δ(G)+8)/10⌋ and Scheide recently improved this bound to χ′(G)>⌊(15Δ(G)+12)/14⌋. We prove this conjecture for multigraphs G with χ′(G)> ⌊ Δ(G)+ Δ(G)/2 ⌋, improving the above mentioned results. As a consequence, for multigraphs G with χ(G)>Delta(G)+sqrt Δ(G)/2} the answer to a 1964 problem of Vizing is in the affirmative. © 2009 Springer Science+Business Media, LLC.en_HK
dc.languageengen_US
dc.publisherSpringer Verlag Dordrecht. The Journal's web site is located at http://springerlink.metapress.com/openurl.asp?genre=journal&issn=1382-6905en_HK
dc.relation.ispartofJournal of Combinatorial Optimizationen_HK
dc.rightsThe original publication is available at www.springerlink.comen_US
dc.subjectChromatic indexen_HK
dc.subjectEdge coloringen_HK
dc.subjectFractional chromatic indexen_HK
dc.subjectMultigraphen_HK
dc.titleApproximating the chromatic index of multigraphsen_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=1382-6905&volume=21&issue=2&spage=219&epage=246&date=2011&atitle=Approximating+the+chromatic+index+of+multigraphs-
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/s10878-009-9232-yen_HK
dc.identifier.scopuseid_2-s2.0-79851515504en_HK
dc.identifier.hkuros190479en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-79851515504&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume21en_HK
dc.identifier.issue2en_HK
dc.identifier.spage219en_HK
dc.identifier.epage246en_HK
dc.identifier.isiWOS:000286680700005-
dc.publisher.placeNetherlandsen_HK
dc.identifier.scopusauthoridChen, G=35794365300en_HK
dc.identifier.scopusauthoridYu, X=7404115058en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.citeulike4740537-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats