Inductive graph invariants and approximation algorithms

DOI10.1142/S1793830922500197zbMath1493.05004OpenAlexW3216461053MaRDI QIDQ5101914

C. R. Subramanian

Publication date: 2 September 2022

Published in: Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s1793830922500197

zbMATH Keywords

degeneracyapproximation algorithmsgraph invariantscombinatorial optimisation\(P\)-colorings\(P\)-subgraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational methods for problems pertaining to combinatorics (05-08)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding a maximum-weight induced \(k\)-partite subgraph of an \(i\)-triangulated graph
• Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs
• The maximum k-colorable subgraph problem for chordal graphs
• Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete
• The ellipsoid method and its consequences in combinatorial optimization
• Some simplified NP-complete graph problems
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• The complexity of \(G\)-free colourability
• Clique is hard to approximate within \(n^{1-\epsilon}\)
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• The complexity of generalized graph colorings
• Tolerance intersection graphs on binary trees with constant tolerance 3
• New approximation guarantee for chromatic number
• Elimination graphs
• Efficient Vertex- and Edge-Coloring of Outerplanar Graphs
• Graph Bipartization and via minimization
• On the computational complexity of (O,P)-partition problems
• Approximation algorithms for NP-complete problems on planar graphs
• Low-degree Graph Partitioning via Local Search with Applications to Constraint Satisfaction, Max Cut, and Coloring
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• The approximation of maximum subgraph problems
• An inequality for the chromatic number of a graph

This page was built for publication: Inductive graph invariants and approximation algorithms