Critical graphs for the chromatic edge-stability number

The chromatic edge-stability number \({\rm es}_{\chi}(G)\) of a graph \(G\) is the minimum number of edges whose removal results in a spanning subgraph \(G'\) with \(\chi(G')=\chi(G)-1\). Edge-stability critical graphs are introduced as the graphs \(G\) with the property that \({\rm es}_{\...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2019-07
Main Authors: Brešar, Boštjan, Klavžar, Sandi, Movarraei, Nazanin
Format: Article
Language:English
Subjects:
Graph theory
Graphs
Polynomials
Stability
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The chromatic edge-stability number \({\rm es}_{\chi}(G)\) of a graph \(G\) is the minimum number of edges whose removal results in a spanning subgraph \(G'\) with \(\chi(G')=\chi(G)-1\). Edge-stability critical graphs are introduced as the graphs \(G\) with the property that \({\rm es}_{\chi}(G-e) < {\rm es}_{\chi}(G)\) holds for every edge \(e\in E(G)\). If \(G\) is an edge-stability critical graph with \(\chi(G)=k\) and \({\rm es}_{\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.
ISSN:2331-8422