+1 Recommend
0 collections
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Vizing-Goldberg type bounds for the equitable chromatic number of block graphs


      , ,

      Read this article at

          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.


          An equitable coloring of a graph \(G\) is a proper vertex coloring of \(G\) such that the sizes of any two color classes differ by at most one. In the paper, we pose a conjecture that offers a gap-one bound for the smallest number of colors needed to equitably color every block graph. In other words, the difference between the upper and the lower bounds of our conjecture is at most one. Thus, in some sense, the situation is similar to that of chromatic index, where we have the classical theorem of Vizing and the Goldberg conjecture for multigraphs. The results obtained in the paper support our conjecture. More precisely, we verify it in the class of well-covered block graphs, which are block graphs in which each vertex belongs to a maximum independent set. We also show that the conjecture is true for block graphs, which contain a vertex that does not lie in an independent set of size larger than two. Finally, we verify the conjecture for some symmetric-like block graphs. In order to derive our results we obtain structural characterizations of block graphs from these classes.

          Related collections

          Author and article information

          24 February 2020


          Custom metadata
          21 pages, 12 figures
          cs.DM math.CO

          Combinatorics, Discrete mathematics & Graph theory


          Comment on this article