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