Critical vertices and edges in \(H\)-free graphs

DOI10.1016/j.dam.2018.08.016zbMath1406.05037arXiv1706.09043OpenAlexW2963297484MaRDI QIDQ1730263

Daniël Paulusma, Christophe Picouleau, Bernard Ries

Publication date: 11 March 2019

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

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

zbMATH Keywords

chromatic numberedge contractionvertex deletion

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Related Items (9)

Reducing the vertex cover number via edge contractions ⋮ The complexity of blocking (semi)total dominating sets with edge contractions ⋮ Reducing the domination number of graphs via edge contractions and vertex deletions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Contraction and deletion blockers for perfect graphs and \(H\)-free graphs ⋮ Blocking total dominating sets via edge contractions ⋮ Reducing graph transversals via edge contractions ⋮ Using edge contractions to reduce the semitotal domination number

Uses Software

• CriticalPfreeGraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On color-critical (\(P_5\),\(\operatorname{co-}P_5\))-free graphs
• Complexity of coloring graphs without paths and cycles
• Minimum \(d\)-blockers and \(d\)-transversals in graphs
• The most vital nodes with respect to independent set and vertex cover
• Blockers for the stability number and the chromatic number
• Blockers and transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid
• On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
• Constructions of \(k\)-critical \(P_5\)-free graphs
• \(d\)-transversals of stable sets and vertex covers in weighted bipartite graphs
• Reducing the chromatic number by vertex or edge deletions
• Reducing the Clique and Chromatic Number via Edge Contractions and Vertex Deletions
• Contraction Blockers for Graphs with Forbidden Induced Paths
• A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
• Blocking Independent Sets for H-Free Graphs via Edge Contractions and Vertex Deletions
• A Certifying Algorithm for 3-Colorability of P 5-Free Graphs
• Obstructions for three-coloring graphs with one forbidden induced subgraph
• Exhaustive generation of k‐critical ‐free graphs
• Minimum vertex blocker clique problem
• On $3$-Colorable $P_5$-Free Graphs
• Hard tiling problems with simple tiles

This page was built for publication: Critical vertices and edges in \(H\)-free graphs