Critical graphs for the chromatic edge-stability number

DOI10.1016/J.DISC.2020.111845zbMATH Open1437.05069arXiv1905.12318OpenAlexW3005502514MaRDI QIDQ2174589FDOQ2174589

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

Publication date: 21 April 2020

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

Abstract: The chromatic edge-stability number ${mes}_{chi}(G)$ of a graph $G$ is the minimum number of edges whose removal results in a spanning subgraph $G^{\prime }$ with $chi(G^{\prime })=chi(G)-1$. Edge-stability critical graphs are introduced as the graphs $G$ with the property that ${mes}_{chi}(G-e)<{mes}_{chi}(G)$ holds for every edge $einE(G)$. If $G$ is an edge-stability critical graph with $chi(G)=k$ and ${mes}_{chi}(G)=ell$, then $G$ is $(k,ell)$-critical. Graphs which are $(3,2)$-critical and contain at most four odd cycles are classified. It is also proved that the problem of deciding whether a graph $G$ has $chi(G)=k$ and is critical for the chromatic number can be reduced in polynomial time to the problem of deciding whether a graph is $(k,2)$-critical.

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

Recommendations

• On critical graphs for the chromatic edge-stability number
• On the chromatic edge stability number of graphs
• On the chromatic edge stability index of graphs
• Some extremal results on the chromatic stability index
• On the \(\rho \)-edge stability number of graphs

zbMATH Keywords

computational complexityodd cyclechromatic edge-stabilityedge-stability critical graph

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Computing the bipartite edge frustration of fullerene graphs
• Edge-disjoint odd cycles in planar graphs.
• Bipartizing fullerenes
• The bipartite edge frustration of graphs under subdivided edges and their related sums
• Double-critical graph conjecture for claw-free graphs
• A relaxed version of the Erdős-Lovász Tihany conjecture
• Bipartite subgraphs of triangle-free subcubic graphs
• Characterizing 4-critical graphs with Ore-degree at most seven
• Optimal packings of edge-disjoint odd cycles
• Title not available (Why is that?)
• On the chromatic edge stability number of graphs
• 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

Cited In (15)

• On the edge chromatic vertex stability number of graphs
• Some extremal results on the chromatic stability index
• On Chromatic Vertex Stability of 3-Chromatic Graphs With Maximum Degree 4
• Nordhaus-Gaddum and other bounds for the chromatic edge-stability number
• On the chromatic vertex stability number of graphs
• Complexity of stability
• Reducing the chromatic number by vertex or edge deletions
• On the chromatic edge stability number of graphs
• On critical graphs for the chromatic edge-stability number
• On the vertex stability numbers of graphs
• Blockers for the stability number and the chromatic number
• A Gallai’s Theorem type result for the edge stability of graphs
• On the Total Chromatic Edge Stability Number and the Total Chromatic Subdivision Number of Graphs
• Edge‐chromatic critical graphs and the existence of 1‐factors
• On the chromatic edge stability index of graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2174589)