کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419344 | 683788 | 2014 | 14 صفحه PDF | دانلود رایگان |
A bb-coloring of a graph GG by kk colors is a proper vertex coloring such that every color class contains a color-dominating vertex, that is, a vertex having neighbors in all other k−1k−1 color classes. The bb-chromatic number χb(G)χb(G) is the maximum integer kk for which GG has a bb-coloring by kk colors. For a bipartite graph G=(A∪B,E)G=(A∪B,E), the bicomplement of GG is the bipartite graph G˜=(A∪B,E˜) with E˜:={{a,b}∣a∈A,b∈B,{a,b}∉E}. In this paper, we investigate the bb-chromatic number for bipartite graphs with a special bicomplement. In particular, we consider graphs GG for which G˜ is disconnected or has maximum degree Δ(G˜)≤2. Moreover, we give partial answers to the question “Which dd-regular bipartite graphs GG satisfy χb(G)=d+1χb(G)=d+1?” and we show a Nordhaus–Gaddum-type result for GG and G˜.
Journal: Discrete Applied Mathematics - Volume 163, Part 2, 30 January 2014, Pages 113–126