Critical graphs for the chromatic edge-stability number

DOI10.1016/j.disc.2020.111845zbMath1437.05069arXiv1905.12318OpenAlexW3005502514MaRDI QIDQ2174589

Nazanin Movarraei, Sandi Klavžar, Boštjan Brešar

Publication date: 21 April 2020

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

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

zbMATH Keywords

computational complexityodd cyclechromatic edge-stabilityedge-stability critical graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

On the chromatic vertex stability number of graphs ⋮ On the Total Chromatic Edge Stability Number and the Total Chromatic Subdivision Number of Graphs ⋮ A Gallai’s Theorem type result for the edge stability of graphs ⋮ On the chromatic edge stability index of graphs ⋮ On the vertex stability numbers of graphs ⋮ On critical graphs for the chromatic edge-stability number ⋮ SOME EXTREMAL RESULTS ON THE CHROMATIC STABILITY INDEX

Cites Work

• Unnamed Item
• Unnamed Item
• Bipartizing fullerenes
• Double-critical graph conjecture for claw-free graphs
• The bipartite edge frustration of graphs under subdivided edges and their related sums
• Characterizing 4-critical graphs with Ore-degree at most seven
• Edge-disjoint odd cycles in planar graphs.
• On the chromatic edge stability number of graphs
• A Brooks-type result for sparse critical graphs
• Optimal packings of edge-disjoint odd cycles
• Nordhaus-Gaddum and other bounds for the chromatic edge-stability number
• The minimum number of edges in a 4-critical graph that is bipartite plus 3 edges
• Computing the bipartite edge frustration of fullerene graphs
• Bipartite subgraphs of triangle-free subcubic graphs
• A Relaxed Version of the Erdős–Lovász Tihany Conjecture

This page was built for publication: Critical graphs for the chromatic edge-stability number