Maximum \(h\)-colourable subgraph problem in balanced graphs

DOI10.1016/S0020-0190(98)00019-2zbMath1338.68098OpenAlexW2029818886MaRDI QIDQ293269

Paul D. Manuel, Mirka Miller, Elias Dahlhaus

Publication date: 9 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: http://www.sciencedirect.com/science/article/pii/S0020019098000192?np=y

zbMATH Keywords

totally balanced matrix\(k\)-fold clique transversal problembalanced graphbalanced matrixmaximum \(h\)-colourable subgraph problemstrongly chordal graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (18)

The algorithmic complexity of the minus clique-transversal problem ⋮ Clique-transversal number of graphs whose clique-graphs are trees ⋮ Clique-perfectness and balancedness of some graph classes ⋮ On some graph classes related to perfect graphs: a survey ⋮ Weighted maximum-clique transversal sets of graphs ⋮ Variations of maximum-clique transversal sets on graphs ⋮ Clique-transversal sets and clique-coloring in planar graphs ⋮ The maximum vertex coverage problem on bipartite graphs ⋮ Algorithms for finding clique-transversals of graphs ⋮ Bounds on the clique-transversal number of regular graphs ⋮ Clique-perfectness of claw-free planar graphs ⋮ Distance-hereditary graphs are clique-perfect ⋮ Unnamed Item ⋮ Algorithms for clique-independent sets on subclasses of circular-arc graphs ⋮ On minimal forbidden subgraph characterizations of balanced graphs ⋮ Clique-perfectness of complements of line graphs ⋮ The clique-perfectness and clique-coloring of outer-planar graphs ⋮ On balanced graphs

Cites Work

• The maximum k-colorable subgraph problem for chordal graphs
• Generalized vertex covering in interval graphs
• The complexity of generalized clique covering
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Maximum \(h\)-colourable subgraph problem in balanced graphs