# zbMATH — the first resource for mathematics

Maximum $$h$$-colourable subgraph problem in balanced graphs. (English) Zbl 1338.68098
Summary: The $$k$$-fold clique transversal problem is to locate a minimum set $$\Omega$$ of vertices of a graph such that every maximal clique has at least $$k$$ elements of $$\Omega$$. The maximum $$h$$-colourable subgraph problem is to find a maximum subgraph of a graph which is $$h$$-colourable. We show that the $$k$$-fold clique transversal problem and the maximum $$h$$-colourable subgraph problem are polynomially solvable on balanced graphs. We also provide a polynomial algorithm to recognize balanced graphs.

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 05C15 Coloring of graphs and hypergraphs 05C35 Extremal problems in graph theory 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) 05C85 Graph algorithms (graph-theoretic aspects)
Full Text:
##### References:
  Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029  Chang, M.S.; Chang, G.J.; Chen, Y.H.; Yan, J.H., Algorithmic aspects of the generalized clique transversal problem on chordal graphs, (), 103-111, Taiwan  Corneil, D.G.; Fonlupt, J., The complexity of generalized clique covering, Discrete appl. math., 22, 109-118, (1989) · Zbl 0685.68046  Fulkerson, D.R.; Hoffman, A.J.; Oppenheim, R., On balanced matrices, math. programming study, 1, 120-132, (1974)  Marathe, M.V.; Ravi, R.; Pandurangan, C., Generalized vertex covering in interval graphs, Discrete applied mathematics, 39, 87-90, (1992) · Zbl 0766.05082  Prisner, E., Hereditarily clique Helly graphs, J. combin. math. combin. comput., 14, 216-220, (1993) · Zbl 0794.05113  Yannakakis, M.; Gavril, F., The maximum k-colourable subgraph problem for chordal graphs, Inform. process. lett., 24, 133-137, (1987) · Zbl 0653.68070
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.