کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418371 | 681656 | 2013 | 7 صفحه PDF | دانلود رایگان |

The b-chromatic number χb(G)χb(G) of a graph GG is the maximum kk 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 xyxy, and for every ii there exists a vertex xx assigned ii adjacent to some vertex yy assigned jj for any j≠ij≠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 GG and m(G)m(G) is the largest integer mm such that GG has at least mm vertices of degree at least m−1m−1. A graph GG is tight if there are exactly m(G)m(G) vertices of degree m(G)−1m(G)−1 and all other vertices have degree less than m(G)−1m(G)−1. This paper discusses a relation between b-chromatic numbers of tight bipartite graphs and the Erdős–Faber–Lovász Conjecture.
Journal: Discrete Applied Mathematics - Volume 161, Issues 7–8, May 2013, Pages 1060–1066