Some problems on induced subgraphs

DOI10.1016/j.dam.2017.10.021zbMath1377.05071arXiv1612.09349OpenAlexW2569075751MaRDI QIDQ1693168

Vaidy Sivaraman

Publication date: 11 January 2018

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1612.09349

zbMATH Keywords

NP-completenesschromatic numberclique numberperfect graphinduced subgraphforbidden induced subgraph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Related Items (3)

2-divisibility of some odd hole free graphs ⋮ Divisibility and coloring of some \(P_5\)-free graphs ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey

Cites Work

• Unnamed Item
• Unnamed Item
• Induced subgraphs of graphs with large chromatic number. I. Odd holes
• Ramsey-type theorems
• On rigid circuit graphs
• Weakly triangulated graphs
• Bisimplicial vertices in even-hole-free graphs
• \(K_{4}\)-free graphs with no odd holes
• Finding large holes
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard
• Bounded clique cover of some sparse graphs
• Recognizing Berge graphs
• On the divisibility of graphs

This page was built for publication: Some problems on induced subgraphs