Balanced edge colorings

P. N. Balister, A. Kostochka, Hao Li, R. H. Schelp

Research output: Contribution to journalArticle

Abstract

This paper contains two principal results. The first proves that any graph G can be given a balanced proper edge coloring by k colors for any k ≥ χ′ (G). Here balanced means that the number of vertices incident with any set of d colors is essentially fixed for each d, that is, for two different d-sets of colors the number of vertices incident with each of them can differ by at most 2. The second result gives upper bounds for the vertex-distinguishing edge chromatic number of graphs G with few vertices of low degree. In particular, it proves a conjecture of Burris and Schelp in the case when Δ(G) ≥ 2 V(G) + 4 and δ(G) ≥ 5.

Original languageEnglish (US)
Pages (from-to)3-20
Number of pages18
JournalJournal of Combinatorial Theory. Series B
Volume90
Issue number1
DOIs
StatePublished - Jan 2004
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Balanced edge colorings'. Together they form a unique fingerprint.

  • Cite this