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.

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: DOI Link
[1] Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029
[2] 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
[3] Corneil, D.G.; Fonlupt, J., The complexity of generalized clique covering, Discrete appl. math., 22, 109-118, (1989) · Zbl 0685.68046
[4] Fulkerson, D.R.; Hoffman, A.J.; Oppenheim, R., On balanced matrices, math. programming study, 1, 120-132, (1974)
[5] Marathe, M.V.; Ravi, R.; Pandurangan, C., Generalized vertex covering in interval graphs, Discrete applied mathematics, 39, 87-90, (1992) · Zbl 0766.05082
[6] Prisner, E., Hereditarily clique Helly graphs, J. combin. math. combin. comput., 14, 216-220, (1993) · Zbl 0794.05113
[7] 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.