On the b-coloring of tight graphs

Mekkia Kouider () and Mohamed Zamime ()
Additional contact information
Mekkia Kouider: Université Paris-Sud
Mohamed Zamime: Université de Médéa

Journal of Combinatorial Optimization, 2017, vol. 33, issue 1, No 14, 202-214

Abstract: Abstract A coloring c of a graph $$G=(V,E)$$ G = ( V , E ) is a b -coloring if for every color i there is a vertex, say w(i), of color i whose neighborhood intersects every other color class. The vertex w(i) is called a b-dominating vertex of color i. The b -chromatic number of a graph G, denoted by b(G), is the largest integer k such that G admits a b-coloring with k colors. Let m(G) be the largest integer m such that G has at least m vertices of degree at least $$m-1$$ m - 1 . A graph G is tight if it has exactly m(G) vertices of degree $$m(G)-1$$ m ( G ) - 1 , and any other vertex has degree at most $$m(G)-2$$ m ( G ) - 2 . In this paper, we show that the b-chromatic number of tight graphs with girth at least 8 is at least $$m(G)-1$$ m ( G ) - 1 and characterize the graphs G such that $$b(G)=m(G)$$ b ( G ) = m ( G ) . Lin and Chang (2013) conjectured that the b-chromatic number of any graph in $$\mathcal {B}_{m}$$ B m is m or $$m-1$$ m - 1 where $$\mathcal {B}_{m}$$ B m is the class of tight bipartite graphs $$(D,D{^\prime })$$ ( D , D ′ ) of girth 6 such that D is the set of vertices of degree $$m-1$$ m - 1 . We verify the conjecture of Lin and Chang for some subclass of $$\mathcal {B}_{m}$$ B m , and we give a lower bound for any graph in $$\mathcal {B}_{m}$$ B m .

Keywords: Coloring; b-coloring; b-chromatic number; Tight graphs; 05C15 (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-015-9946-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:33:y:2017:i:1:d:10.1007_s10878-015-9946-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-015-9946-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().