Originators: A. El-Sahili and M. Kouider (2006) (presented by Suil O - REGS 2010)
Definitions: The chromatic number of a graph G, written χ(G), is the least number of colors in a proper coloring of the vertices (adjacent vertices receiving distinct colors). The a-chromatic number, written χa(G), is the largest number of colors in a proper coloring such that for any two color classes, some edge has endpoints in both. The b-chromatic number, written χb(G), is the largest number of colors in a proper coloring such that each color class has a vertex with neighbors in all other classes. (Some authors use a(G) and b(G) instead of χa(G) and χb(G).) Since every b-coloring is a proper coloring and is also an a-coloring, always χ(G)≤χb(G)≤χa(G).
Background:
One way to find a proper coloring of a graph is to start with distinct colors
on the vertices and iteratively decrease the number of colors by combining two
colors when no edge has endpoints in both. When the process stops, the
resulting coloring is an a-coloring. Harary and Hedetniemi [HH]
introduced the a-chromatic number to measure how badly this procedure
can perform.
Another way to seek a proper coloring with few colors is to iteratively
eliminate colors by transferring each vertex in a fixed color class to another
color class in which it has no neighbors. When the process stops, the
resulting coloring is an b-coloring. Irving and Manlove [IM] introduced
the b-chromatic number to measure how badly this procedure can perform.
Since each color class in a largest b-coloring has a vertex with degree
at least χb(G)-1, always
χb(G)≤Δ(G)+1.
Conjecture 1: If G is a d-regular graph with girth at least 5 that is not the Petersen graph, then the b-chromatic number of G is d+1.
Question 2: (Suil O) For d-regular bipartite graphs, what girth is needed to guarantee that the b-chromatic number is d+1?
Comment: All that remains to prove Conjecture 1 is the case of graphs with girth equal to 5 that also contain a 6-cycle. Also, Blidia, Maffray, and Zemir [BMZ] proved Conjecture 1 for d∈{3,4,5,6}. For the Petersen graph, the b-chromatic number is 3 and the a-chromatic number is 5. Thus there may be a gap between χa(G) and χb(G).
For these three coloring parameters, the maximum sum of the values on an n-vertex graph and its complement are known. For both χ and χb, the maximum is n+1, proved by Nordhaus and Gaddum [NG] and by Kouider and Maheo [KM], respectively. Equality holds when G is Kr plus n-r isolated vertices. For the a-chromatic number, Gupta [G] proved that χa(G)+χa(Gc)≤(4/3)n, and this also is sharp.
The Kneser graph, written K(n,k), is the graph whose vertices are the k-element subsets of 1,…n, with the adjacency relation given by disjointness of sets. The Petersen graph is K(5,2).
Problem 3: What is the b-chromatic number of the Kneser graph K(n,k)?
Comment: The b-chromatic number of K(n,2) and K(2k+1,k) were determined by Javadi and Omoomi [JO]. The graph K(2k+1,k) is (k+1)-regular and has girth 6, so the known cases of Conjecture 1 show that its b-chromatic number is k+2. When n>2k+1, the girth of K(n,k) is 4, and the b-chromatic number need not equal the degree plus 1. Indeed, [JO] showed that χb(K(n,2)) is ⌊n(n-1)/6⌋ if n is odd, and it is ⌊(n-1)(n-2)/6⌋ if n is even.
References:
[BMZ] M. Blidia, F. Maffray, and Z. Zemir, On b-Colorings in Regular Graphs,
Discrete Applied Mathematics. 157 (2009) 1787-1793
[G] R.P. Gupta, Bounds on the Chromatic and Achromatic Numbers of
Complementary Graphs. Recent Progress in Combinatorics
(W. T. Tutte, ed.), Academic Press, New York, 1969
[HH] F. Harary and S. Hedetniemi, The Achromatic Number of a Graph, Journal of
Combinatorial Theory 8 (1970), 154-161
[IM] R.W. Irving and D.F. Manlove, The b-Chromatic Number of Graphs,
Discrete Appl. Math. 91 (1999), no. 1-3, 127--141.
[JO] R. Javadi, B. Omoomi, On b-coloring of the Kneser graphs, Discrete
Mathematics. 309 (2009) 4399 -4408.
[KM] M. Kouider and M. Maheo, Some bounds for the b-chromatic number of
a graph, Discrete Mathematics 256 (2002) 267-277
[NG] Nordhaus, E. A.; Gaddum, J. W. On complementary graphs.
Amer. Math. Monthly 63 (1956), 175--177.