The maximum k-colorable subgraph problem for chordal graphs

DOI10.1016/0020-0190(87)90107-4zbMath0653.68070OpenAlexW2062221600MaRDI QIDQ1108038

Publication date: 1987

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

Full work available at URL: https://doi.org/10.1016/0020-0190(87)90107-4

zbMATH Keywords

chordal graphs NP-complete k-colorable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

Faster exact algorithms for some terminal set problems ⋮ MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS ⋮ A faster algorithm to recognize undirected path graphs ⋮ A linear-time algorithm for the weighted feedback vertex problem on interval graphs ⋮ Maximum $h$-colourable subgraph problem in balanced graphs ⋮ Reconfiguration of colorable sets in classes of perfect graphs ⋮ On the $k$-coloring of intervals ⋮ Heterogeneous Multi-resource Allocation with Subset Demand Requests ⋮ Inverse chromatic number problems in interval and permutation graphs ⋮ Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ New upper bounds on feedback vertex numbers in butterflies ⋮ Fixed interval scheduling: models, applications, computational complexity and algorithms ⋮ Refined algorithms for hitting many intervals ⋮ Optimal channel allocation for several types of cellular radio networks ⋮ On the Generalized $\vartheta$-Number and Related Problems for Highly Symmetric Graphs ⋮ Parameterized and exact algorithms for class domination coloring ⋮ Algorithmic aspects of the generalized clique-transversal problem on chordal graphs ⋮ Approximation results for the optimum cost chromatic partition problem ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ The off-line group seat reservation problem ⋮ Inductive graph invariants and approximation algorithms ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ Large Induced Subgraphs via Triangulations and CMSO ⋮ Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs ⋮ Scheduling to Maximize the Number of Just-in-Time Jobs: A Survey ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ Exact algorithms for restricted subset feedback vertex set in chordal and split graphs ⋮ The just-in-time scheduling problem in a flow-shop scheduling system ⋮ Approximate minimum sum colorings and maximum $k$-colorable subgraphs of chordal graphs ⋮ Graph coloring with rejection ⋮ Maximizing the weighted number of just-in-time jobs in~several two-machine scheduling systems ⋮ Parameterized and Exact Algorithms for Class Domination Coloring ⋮ Fair allocation of indivisible items with conflict graphs ⋮ A sequential algorithm for finding a maximum weightK-independent set on interval graphs ⋮ The maximum vertex coverage problem on bipartite graphs ⋮ On the complexity of the selective graph coloring problem in some special classes of graphs ⋮ Algorithmic aspects of clique-transversal and clique-independent sets ⋮ Solving the single step graph searching problem by solving the maximum two-independent set problem ⋮ Clique partitioning of interval graphs with submodular costs on the cliques ⋮ The 0-1 inverse maximum stable set problem ⋮ An efficient algorithm for finding a maximum weight 2-independent set on interval graphs ⋮ Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes ⋮ Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs ⋮ Minimum Entropy Combinatorial Optimization Problems ⋮ Minimum weight feedback vertex sets in circle graphs ⋮ Minimum entropy combinatorial optimization problems ⋮ Efficient algorithms for the double traveling salesman problem with multiple stacks ⋮ Just-in-time scheduling with controllable processing times on parallel machines ⋮ Approximating maximum weight $K$-colorable subgraphs in chordal graphs ⋮ Unnamed Item ⋮ Contracting chordal graphs and bipartite graphs to paths and trees ⋮ Vertex deletion problems on chordal graphs ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ “Rent-or-Buy” Scheduling and Cost Coloring Problems ⋮ The complexity of generalized clique covering ⋮ Maximizing dominance in the plane and its applications ⋮ Contracting chordal graphs and bipartite graphs to paths and trees ⋮ Maximum weightk-independent set problem on permutation graphs ⋮ Weighted sum coloring in batch scheduling of conflicting jobs ⋮ Inductive $k$-independent graphs and $c$-colorable subgraphs in scheduling: a review ⋮ Characterization of QUBO reformulations for the maximum $k$-colorable subgraph problem ⋮ Vertex Deletion Problems on Chordal Graphs

Cites Work