### 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 language | English |
---|---|

Pages (from-to) | 1060-1066 |

Number of pages | 7 |

Journal | Discrete Applied Mathematics |

Volume | 161 |

Issue number | 7-8 |

DOIs | |

State | Published - 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

*Discrete Applied Mathematics*,

*161*(7-8), 1060-1066. https://doi.org/10.1016/j.dam.2012.11.012