Edge coloring multigraphs without small dense subsets

P. E. Haxell, Henry Kierstead

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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 languageEnglish (US)
Pages (from-to)2502-2506
Number of pages5
JournalDiscrete Mathematics
Issue number12
StatePublished - Jul 13 2015


  • Edge coloring
  • Goldberg's conjecture
  • Multigraphs

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Edge coloring multigraphs without small dense subsets'. Together they form a unique fingerprint.

Cite this