Add to ORKGA vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by one. We consider the problems of deciding whether a graph has a critical vertex or edge, respectively. We give a complexity dichotomy for both problems restricted to H-free graphs, that is, graphs with no induced subgraph isomorphic to H. Moreover, we show that an edge is critical if and only if its contraction reduces the chromatic number by one. Hence, we also obtain a complexity dichotomy for the problem of deciding if a graph has an edge whose contraction reduces the chromatic number by one
For a graph H, the H-free Edge Deletion problem asks whether there exist at most k edges whose delet...
AbstractA graph G is called k-critical if G is k-chromatic but every proper subgraph of G has chroma...
In this paper, we study the problem of deciding whether the total domination number of a given grap...
A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by...
A vertex or an edge in a graph is critical if its deletion reduces the chromatic number of the graph...
This thesis comprises two parts. In the first part, we study classical, parameterized and kernelizat...
The classical stability theorem of Erd˝os and Simonovits states that, for any fixed graph with chrom...
Given two graphs H1 and H2, a graph G is (H1, H2)-free if it contains no induced subgraph isomorphic...
International audienceA b-coloring of a graph G is a proper coloring of the vertices of G such that ...
A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex t...
In graph theory, the term critical is usually used with respect to specified graph parameter P and ...
Abstract. A b-coloring is a coloring of the vertices of a graph such that each color class contains ...
AbstractIt is shown that the minimal number of edges which have to be omitted from a (k + 1)-critica...
AbstractThis paper presents algorithms to find vertex-critical and edge-critical subgraphs in a give...
For a graph H, the H-free Edge Deletion problem asks whether there exist at most k edges whose delet...
For a graph H, the H-free Edge Deletion problem asks whether there exist at most k edges whose delet...
AbstractA graph G is called k-critical if G is k-chromatic but every proper subgraph of G has chroma...
In this paper, we study the problem of deciding whether the total domination number of a given grap...
A vertex or edge in a graph is critical if its deletion reduces the chromatic number of the graph by...
A vertex or an edge in a graph is critical if its deletion reduces the chromatic number of the graph...
This thesis comprises two parts. In the first part, we study classical, parameterized and kernelizat...
The classical stability theorem of Erd˝os and Simonovits states that, for any fixed graph with chrom...
Given two graphs H1 and H2, a graph G is (H1, H2)-free if it contains no induced subgraph isomorphic...
International audienceA b-coloring of a graph G is a proper coloring of the vertices of G such that ...
A b-coloring is a coloring of the vertices of a graph such that each color class contains a vertex t...
In graph theory, the term critical is usually used with respect to specified graph parameter P and ...
Abstract. A b-coloring is a coloring of the vertices of a graph such that each color class contains ...
AbstractIt is shown that the minimal number of edges which have to be omitted from a (k + 1)-critica...
AbstractThis paper presents algorithms to find vertex-critical and edge-critical subgraphs in a give...
For a graph H, the H-free Edge Deletion problem asks whether there exist at most k edges whose delet...
For a graph H, the H-free Edge Deletion problem asks whether there exist at most k edges whose delet...
AbstractA graph G is called k-critical if G is k-chromatic but every proper subgraph of G has chroma...
In this paper, we study the problem of deciding whether the total domination number of a given grap...