An improved bound on the minimal number of edges in color-critical graphs.

Krivelevich, Michael

Displaying similar documents to “An improved bound on the minimal number of edges in color-critical graphs.”

On the Independence Number of Edge Chromatic Critical Graphs

Shiyou Pang, Lianying Miao, Wenyao Song, Zhengke Miao (2014)

Discussiones Mathematicae Graph Theory

Similarity:

In 1968, Vizing conjectured that for any edge chromatic critical graph G = (V,E) with maximum degree △ and independence number α (G), α (G) ≤ [...] . It is known that α (G) < [...] |V |. In this paper we improve this bound when △≥ 4. Our precise result depends on the number n2 of 2-vertices in G, but in particular we prove that α (G) ≤ [...] |V | when △ ≥ 5 and n2 ≤ 2(△− 1)

Towards the Albertson conjecture.

Barát, János, Tóth, Géza (2010)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

The Connectivity Of Domination Dot-Critical Graphs With No Critical Vertices

Michitaka Furuya (2014)

Discussiones Mathematicae Graph Theory

Similarity:

An edge of a graph is called dot-critical if its contraction decreases the domination number. A graph is said to be dot-critical if all of its edges are dot-critical. A vertex of a graph is called critical if its deletion decreases the domination number. In A note on the domination dot-critical graphs, Discrete Appl. Math. 157 (2009) 3743-3745, Chen and Shiu constructed for each even integer k ≥ 4 infinitely many k-dot-critical graphs G with no critical vertices and k(G) = 1. In this...

Double-critical graphs and complete minors.

Kawarabayashi, Ken-Ichi, Pedersen, Anders Sune, Toft, Bjarne (2010)

The Electronic Journal of Combinatorics [electronic only]

Similarity:

Partition numbers, connectivity and Hamiltonicity

Mieczysław Borowiecki (1987)

Časopis pro pěstování matematiky

Similarity:

A characterization of diameter-2-critical graphs with no antihole of length four

Teresa Haynes, Michael Henning (2012)

Open Mathematics

Similarity:

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As...

On cotree-critical and DFS cotree-critical graphs.

de Fraysseix, Hubert, Ossona de Mendez, Patrice (2003)

Journal of Graph Algorithms and Applications

Similarity:

The diameter of paired-domination vertex critical graphs

Michael A. Henning, Christina M. Mynhardt (2008)

Czechoslovak Mathematical Journal

Similarity:

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks (1998), 199–206). A paired-dominating set of a graph $G$ with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of $G$ , denoted by $γ_{pr} (G)$ , is the minimum cardinality of a paired-dominating set of $G$ . The graph $G$ is paired-domination vertex critical if for every vertex $v$ of $G$ that is not adjacent to a vertex of...