- Source: Critical graph
In graph theory, a critical graph is an undirected graph all of whose proper subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. Each time a single edge or vertex (along with its incident edges) is removed from a critical graph, the decrease in the number of colors needed to color that graph cannot be by more than one.
Variations
A
k
{\displaystyle k}
-critical graph is a critical graph with chromatic number
k
{\displaystyle k}
. A graph
G
{\displaystyle G}
with chromatic number
k
{\displaystyle k}
is
k
{\displaystyle k}
-vertex-critical if each of its vertices is a critical element. Critical graphs are the minimal members in terms of chromatic number, which is a very important measure in graph theory.
Some properties of a
k
{\displaystyle k}
-critical graph
G
{\displaystyle G}
with
n
{\displaystyle n}
vertices and
m
{\displaystyle m}
edges:
G
{\displaystyle G}
has only one component.
G
{\displaystyle G}
is finite (this is the De Bruijn–Erdős theorem).
The minimum degree
δ
(
G
)
{\displaystyle \delta (G)}
obeys the inequality
δ
(
G
)
≥
k
−
1
{\displaystyle \delta (G)\geq k-1}
. That is, every vertex is adjacent to at least
k
−
1
{\displaystyle k-1}
others. More strongly,
G
{\displaystyle G}
is
(
k
−
1
)
{\displaystyle (k-1)}
-edge-connected.
If
G
{\displaystyle G}
is a regular graph with degree
k
−
1
{\displaystyle k-1}
, meaning every vertex is adjacent to exactly
k
−
1
{\displaystyle k-1}
others, then
G
{\displaystyle G}
is either the complete graph
K
k
{\displaystyle K_{k}}
with
n
=
k
{\displaystyle n=k}
vertices, or an odd-length cycle graph. This is Brooks' theorem.
2
m
≥
(
k
−
1
)
n
+
k
−
3
{\displaystyle 2m\geq (k-1)n+k-3}
.
2
m
≥
(
k
−
1
)
n
+
⌊
(
k
−
3
)
/
(
k
2
−
3
)
⌋
n
{\displaystyle 2m\geq (k-1)n+\lfloor (k-3)/(k^{2}-3)\rfloor n}
.
Either
G
{\displaystyle G}
may be decomposed into two smaller critical graphs, with an edge between every pair of vertices that includes one vertex from each of the two subgraphs, or
G
{\displaystyle G}
has at least
2
k
−
1
{\displaystyle 2k-1}
vertices. More strongly, either
G
{\displaystyle G}
has a decomposition of this type, or for every vertex
v
{\displaystyle v}
of
G
{\displaystyle G}
there is a
k
{\displaystyle k}
-coloring in which
v
{\displaystyle v}
is the only vertex of its color and every other color class has at least two vertices.
Graph
G
{\displaystyle G}
is vertex-critical if and only if for every vertex
v
{\displaystyle v}
, there is an optimal proper coloring in which
v
{\displaystyle v}
is a singleton color class.
As Hajós (1961) showed, every
k
{\displaystyle k}
-critical graph may be formed from a complete graph
K
k
{\displaystyle K_{k}}
by combining the Hajós construction with an operation that identifies two non-adjacent vertices. The graphs formed in this way always require
k
{\displaystyle k}
colors in any proper coloring.
A double-critical graph is a connected graph in which the deletion of any pair of adjacent vertices decreases the chromatic number by two. It is an open problem to determine whether
K
k
{\displaystyle K_{k}}
is the only double-critical
k
{\displaystyle k}
-chromatic graph.
See also
Factor-critical graph
References
Further reading
Kata Kunci Pencarian:
- Globalisasi
- Pasukan Pertahanan Israel
- Posthumanisme
- Montenegro
- Teorema empat warna
- Daftar masalah matematika yang belum terpecahkan
- Orang Yunani
- Bentley Systems
- Dewan Pengawas (Meta)
- Critical graph
- Glossary of graph theory
- Factor-critical graph
- List of graph theory topics
- Graph coloring
- Critical point (mathematics)
- Component (graph theory)
- Directed acyclic graph
- Graph of a function
- Graph theory
