Edge coloring multigraphs without small dense subsets

P. E. Haxell; Henry Kierstead

doi:10.1016/j.disc.2015.06.022

Edge coloring multigraphs without small dense subsets

P. E. Haxell, Henry Kierstead

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

Abstract

One consequence of a long-standing conjecture of Goldberg and Seymour about the chromatic index of multigraphs would be the following statement. Suppose G is a multigraph with maximum degree Δ, such that no vertex subset S of odd size at most Δ induces more than (Δ+1)(|S|-1)/2 edges. Then G has an edge coloring with Δ+1 colors. Here we prove a weakened version of this statement.

Original language	English (US)
Pages (from-to)	2502-2506
Number of pages	5
Journal	Discrete Mathematics
Volume	338
Issue number	12
DOIs	https://doi.org/10.1016/j.disc.2015.06.022
State	Published - Jul 13 2015

Keywords

Edge coloring
Goldberg's conjecture
Multigraphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2015.06.022

Cite this

@article{6c34128313df48dd8b69047b3c8b4132,

title = "Edge coloring multigraphs without small dense subsets",

abstract = "One consequence of a long-standing conjecture of Goldberg and Seymour about the chromatic index of multigraphs would be the following statement. Suppose G is a multigraph with maximum degree Δ, such that no vertex subset S of odd size at most Δ induces more than (Δ+1)(|S|-1)/2 edges. Then G has an edge coloring with Δ+1 colors. Here we prove a weakened version of this statement.",

keywords = "Edge coloring, Goldberg's conjecture, Multigraphs",

author = "Haxell, {P. E.} and Henry Kierstead",

year = "2015",

month = jul,

day = "13",

doi = "10.1016/j.disc.2015.06.022",

language = "English (US)",

volume = "338",

pages = "2502--2506",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "12",

}

TY - JOUR

T1 - Edge coloring multigraphs without small dense subsets

AU - Haxell, P. E.

AU - Kierstead, Henry

PY - 2015/7/13

Y1 - 2015/7/13

N2 - One consequence of a long-standing conjecture of Goldberg and Seymour about the chromatic index of multigraphs would be the following statement. Suppose G is a multigraph with maximum degree Δ, such that no vertex subset S of odd size at most Δ induces more than (Δ+1)(|S|-1)/2 edges. Then G has an edge coloring with Δ+1 colors. Here we prove a weakened version of this statement.

AB - One consequence of a long-standing conjecture of Goldberg and Seymour about the chromatic index of multigraphs would be the following statement. Suppose G is a multigraph with maximum degree Δ, such that no vertex subset S of odd size at most Δ induces more than (Δ+1)(|S|-1)/2 edges. Then G has an edge coloring with Δ+1 colors. Here we prove a weakened version of this statement.

KW - Edge coloring

KW - Goldberg's conjecture

KW - Multigraphs

UR - http://www.scopus.com/inward/record.url?scp=84937061156&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84937061156&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2015.06.022

DO - 10.1016/j.disc.2015.06.022

M3 - Article

AN - SCOPUS:84937061156

SN - 0012-365X

VL - 338

SP - 2502

EP - 2506

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 12

ER -

Edge coloring multigraphs without small dense subsets

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this