Question

A graph \(G\) is \(k\)-critical if \(\chi(G)=k\) and if the deletion of any vertex yields a graph with smaller chromatic number. (i) Find all 2 -critical and 3-critical graphs. (ii) Give an example of a 4-critical graph. (iii) Prove that, if \(G\) is \(k\)-critical, then (a) every vertex of \(G\) has degree at least \(k-1\); (b) \(G\) has no cut-vertices.

Short answer

The graphs that are 2-critical are a single edge and a cycle with length greater than or equal to 3. 3-critical graphs are a triangle or a cycle with length greater than or equal to 4. An example of a 4-critical graph is the Kuratowski Graph \(K_5\). If a graph is \(k\)-critical, then every vertex has degree at least \(k-1\) and there are no cut-vertices in the graph.

Step-by-step solution

Part 1: Identifying Graphs

For any graph to be 2-critical, it has to be non-empty and any vertex removal should reduce the chromatic number to 1, which means the graph must resemble a simple chain. These graphs are a single edge and a cycle of length greater than or equal to 3. To be 3-critical, any graph must have a chromatic number of 3 and removing any vertex should reduce the chromatic number to 2. Such graphs can be a triangle or a cycle of length grater than or equal to 4.

Part 2: Example of a 4-critical Graph

In order for a graph to be 4-critical, it must be such that its chromatic number is 4 and any vertex removal ought to reduce the chromatic number to 3 or less. An example would be the Kuratowski Graph \(K_5\).

Part 3: Proving Characteristics of \(k\)-critical Graphs

(a) Proving that every vertex of \(G\) has degree at least \(k-1\). Let's assume there is a vertex \(v\) in \(G\) with degree less than \(k-1\). Remove \(v\), the chromatic number will be less than \(k\) because \(v\) wouldn't be adjacent to \(k\) different colors since its degree was less than \(k-1\). This contradicts our definition of a \(k\)-critical graph. Hence, every vertex in a \(k\)-critical graph has degree atleast \(k-1\). (b) Proving that \(G\) has no cut-vertices. A cut-vertex in a graph is a vertex that, when removed, increases the number of connected components. If \(G\) has a cut-vertex, removing this vertex wouldn't affect the chromatic number because it wouldn't disconnect a color. Also, \(G\) wouldn't be \(k\)-critical, but this contradicts our definition of \(k\)-criticality. Therefore, \(G\) has no cut-vertices.

Key concepts

Chromatic Number

The chromatic number of a graph is a fundamental concept in graph theory. It represents the smallest number of colors needed to color the vertices of a graph so that no two adjacent vertices share the same color. This is crucial in problems that require coloring without conflicts, such as scheduling tasks or coloring maps.

For instance, consider a simple triangle graph. The chromatic number here is 3 because you need three different colors to ensure no two connected vertices (since all vertices are interconnected) are the same color. Other graphs with different structures will have different chromatic numbers.

In the context of the exercise given, a graph is classified as \(k\)-critical if it has a chromatic number \(\chi(G) = k\) and removing any vertex causes the chromatic number to drop below \(k\). Identifying the chromatic number helps understand the coloring complexity of a graph and gives insight into its structure.

Vertex Degree

Vertex degree is another key concept that helps us understand the fundamental properties of graphs. The degree of a vertex in a graph refers to the number of edges that are incident to the vertex. Essentially, it tells us how many connections (or neighbors) a particular vertex has.

For example, in a simple triangle graph, each vertex has a degree of 2 because it is connected to the other two vertices. In more complex structures, the degree of each vertex can vary greatly.

When considering \(k\)-critical graphs, an important property is that every vertex must have a degree of at least \(k - 1\). This is because removing a vertex with fewer connections (less than \(k-1\)) will reduce the chromatic number, contradicting \(k\)-criticality. Therefore, understanding and calculating vertex degrees is vital to exploring graph coloring complexity and ensuring the conditions for \(k\)-critical graphs are met.

Cut-Vertex

A cut-vertex is a unique vertex in a graph that, when removed, causes the graph to become disconnected or increases the number of connected components. This can alter the structure of the graph significantly.

For understanding cut-vertices, consider a simple scenario: a graph that looks like a chain of several links. If you remove a link in the middle, the chain splits into two separate parts, each being a connected component. This removed link is a cut-vertex.

In \(k\)-critical graphs, there cannot be any cut-vertices. The reason is that when a cut-vertex is removed, the resulting graph could potentially maintain its chromatic number, again contradicting the definition of \(k\)-criticality. Therefore, identifying and understanding cut-vertices is essential in confirming whether a graph is \(k\)-critical or not.