The \(b\)-continuity of graphs with large girth (Q1684929): Difference between revisions

A proper vertex coloring of a simple graph \(G\) is called a \(b\)-coloring if there exists a vertex in every color class joined with some vertex in every other color class. The \(b\)-chromatic number of \(G\) is defined as the greatest integer \(b\) such that \(G\) has a \(b\)-coloring. The \(b\)-chromatic number is widely studied widely in the recent years from the computational point of view. Suppose \(G\) has a \(b\)-coloring with \(t\) colors for each integer between \(c\) and \(d\) where \(c\) is the chromatic number and \(d\) is the \(b\)-chromatic number then we call \(G\) a \(b\)-continuous graph. The authors establish that if \(G\) has girth at least 10 then it is \(b\)-continuous. They also made a strong assertion that unlike in the classical coloring problem remaining locally acyclic is conducive to get a \(b\)-coloring of a graph. They also raised some interesting questions like (a) Are regular graphs with girth at least 5 \(b\)-continuous? and (b) Are bipartite graphs with girth at least 6 \(b\)-continuous? and indicated the potential for further research.