8,197 views
Graph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$. The minimum number of colours required to edge-colour $G$ is _______

This question is asking for edge coloring and not vertex coloring.

Had it been asked for vertex coloring, the answer would be $3$ (one color each for the two sets of vertices in given bipartite graph and $1$ color for vertex 's')

Edge coloring for graph is assignment of colors to the graph edges such that no two incident edges have the same color.

The vertex which is a part of highest number of incident edges is 's' as it has an edge to every other vertex of the graph. So there are $7$ incident edges for this vertex and all of them need to be assigned a different/unique color.

So the minimum number of colors needed for edge coloring the given graph is $7.$

-- Edge chromatic number or chromatic index of any simple undirected graph is either $d_{max}$  or $d_{max} + 1$ according to Vizing's Theorem.
https://en.wikipedia.org/wiki/Edge_coloring#Vizing's_theorem
So, here, minimum number of colors can be 7 or 8. So, we have to convince ourselves that minimum number of colors required to proper color the edges of the given graph can't be 8 by making atleast  one graph which required only $7$ colors for proper edge coloring.
https://gateoverflow.in/?qa=blob&qa_blobid=10132893589318938572

-- Suppose, maximum degree of a graph $G$ is $\Delta(G).$
if $|E| > \Delta(G)*\left \lfloor \frac{|V|}{2} \right \rfloor$ then graph $G$ requires $\Delta(G) + 1$ minimum colors for edge coloring of graph. But if $|E| \ngtr \Delta(G)*\left \lfloor \frac{|V|}{2} \right \rfloor$ then graph $G$ requires $\Delta(G)$ . It is wrong statement. Counter-example is Petersen graph with 10 vertices, 15 edges and maximum degree=3. Petersen graph requires 4 colors with maximum degree=3 for proper edge-coloring.

-- All regular graphs $G$ with odd no. of vertices requires $\Delta(G) + 1$ minimum no. of colors for   proper edge-coloring. For example-Triangle.

Plz see both image . . . .

Nice explanation @ankitgupta.

We need to check if 8 colors requires or not.

https://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/coloring.htm

Unfortunately, all the explanations present here are incorrect including the explanation in the “best answer”.

Though I have mentioned the explanation and the example in the form of comment here. But still, I am mentioning the example again here because I feel that after edit that answer with the correct explanation does not make it the “best answer” because this is not a typo, this is a conceptual mistake.

Maximum degree of a graph does not decide the minimum number of colors required to edge-color the simple graph $G.$

For Example, consider a $C_3$ (In the mentioned comment, I have called it as a triangle in the informal way at the end ) as:

This graph has maximum degree as $2$ but it can’t be colored with minimum number of $2$ colors so that adjacent edges have the different colors.

Vizing and Gupta independently proved that $\Delta(G) + 1$ colors suffice when $G$ is simple where $\Delta(G)$ is the maximum degree of a simple graph $G.$

So, if $G$ is simple then $\chi’(G) \leq \Delta(G) + 1$ ($\chi’(G)$ is the edge-chromatic number or chromatic index of the graph $G$)

(Proof is given on wikipedia and in various graph theory books.)

Note:

1. A simple graph $G$ is $\textbf{Class-1}$ if  $\chi’(G) = \Delta(G)$ and $\textbf{Class-2}$ if  $\chi’(G) = \Delta(G) + 1$ and determining whether a graph $G$ is Class-1 or Class-2 is generally hard.
2. If $G$ is bipartite then $\chi’(G) = \Delta(G)$
3. The Petersen Graph is $4-$ edge-chromatic though maximum degree in this graph is $3.$

To proper colour a graph,

For vertex-colouring, we need at least the size of max clique present in the graph.

For edge-colouring, we need at least the max degree of the graph. // Here it is 7

For minimum, we might need one more colour at times. e.g $K_3$, $K-5$

4 colors for edge coloring + 3 colors for the edges connecting the vertex s. The chromatic index or minimum edge colors are 7.

by

1 vote
1
1,864 views