B-coloring of tight bipartite graphs and the Erdös-Faber-Lovász conjecture

Wu-Hsiung Lin*, Gerard J. Chang

*Corresponding author for this work

Research output: Contribution to journalArticle

7 Scopus citations

Abstract

The b-chromatic number χ b (G) of a graph G is the maximum k for which there is a function c;V(G)→{1,2,.,k} such that c(x)≠c(y) for any edge xy, and for every i there exists a vertex x assigned i adjacent to some vertex y assigned j for any j≠i. In general, χ(G) ≤χ b (G)≤m(G)≤Δ(G)+1, where Δ(G) is the maximum degree of G and m(G) is the largest integer m such that G has at least m vertices of degree at least m-1. A graph G is tight if there are exactly m(G) vertices of degree m(G)-1 and all other vertices have degree less than m(G)-1. This paper discusses a relation between b-chromatic numbers of tight bipartite graphs and the Erdös-Faber-Lovász Conjecture.

Original languageEnglish
Pages (from-to)1060-1066
Number of pages7
JournalDiscrete Applied Mathematics
Volume161
Issue number7-8
DOIs
StatePublished - 1 May 2013

Keywords

  • Bipartite graph
  • Dense vertex
  • Tight graph
  • b-coloring

Fingerprint Dive into the research topics of 'B-coloring of tight bipartite graphs and the Erdös-Faber-Lovász conjecture'. Together they form a unique fingerprint.

  • Cite this