The b-chromatic number of a graph

Article English OPEN
Irving, R.W. ; Manlove, D.F. (1999)
  • Publisher: Elsevier
  • Journal: Discrete Applied Mathematics (issn: 0166-218X, vol: 91, pp: 127-141)
  • Related identifiers: doi: 10.1016/S0166-218X(98)00146-2
  • Subject: Applied Mathematics | QA75 | Discrete Mathematics and Combinatorics

The achromatic number psi(G) of a graph G = (V,E) is the maximum k such that V has a partition V1, V2,...,Vk into independent sets, the union of no pair of which is independent. Here we show that psi(G) can be viewed as the maximum over all minimal elements of a partial order defined on the set of all colourings of G. We introduce a natural refinement of this partial order, giving rise to a new parameter, which we call the b-chromatic number, varphi(G), of G. We prove that determining varphi(G) is NP-hard for general graphs, but polynomial-time solvable for trees.
  • References (16)
    16 references, page 1 of 2

    [1] H.L. Bodlaender. Achromatic number is NP-complete for cographs and interval graphs. Information Processing Letters, 31:135{138, 1989.

    [2] N. Cairnie and K. Edwards. Some results on the achromatic number. Journal of Graph Theory, 26:129{136, 1997.

    [3] A. Chaudhary and S. Vishwanathan. Approximation algorithms for the achromatic number. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, pages 557{562. ACM-SIAM, 1997.

    [4] G.A. Cheston, G. Fricke, S.T. Hedetniemi, and D.P. Jacobs. On the computational complexity of upper fractional domination. Discrete Applied Mathematics, 27:195{ 207, 1990.

    [5] C.A. Christen and S.M. Selkow. Some perfect coloring properties of graphs. Journal of Combinatorial Theory, Series B, 27:49{59, 1979.

    [6] M. Farber, G. Hahn, P. Hell, and D. Miller. Concerning the achromatic number of a graph. Journal of Combinatorial Theory, Series B, 40:21{39, 1986.

    [7] M.R. Garey and D.S. Johnson. Computers and Intractability. Freeman, San Francisco, CA., 1979.

    [8] M.M. Halldo┬Ârsson. Approximating the minimum maximal independence number. Information Processing Letters, 46:169{172, 1993.

    [9] F. Harary. Maximum versus minimum invariants for graphs. Journal of Graph Theory, 7:275{284, 1983.

    [10] F. Harary and S. Hedetniemi. The achromatic number of a graph. Journal of Combinatorial Theory, 8:154{161, 1970.

  • Metrics
    No metrics available
Share - Bookmark