GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 28

Question

The edge chromatic number of the following graph is _________

 

Comments

This is complete graph $K_{6}$ and $\left | V \right | $ is even;

for any graph  $K_{n}$ if n is even edge chromatic no. χ′(G) = $\Delta (G)$ which is maximum degree of graph G.

χ′(G)=5

Answer 1

An edge coloring of a graph is an assignment of colors to edges so that edges incident with a common vertex are assigned different colors. The edge chromatic number of a graph $G$ is the smallest number of colors that can be used in an edge coloring of the graph and is denoted by $\chi^{'}(G).$

The edge chromatic number, sometimes also called the chromatic index of a graph must be at least as large as the maximum degree of any vertex of the graph.

Another property of edge coloring is that in a graph $G$ with $n$ vertices, no more than $\frac{n}{2}$ edges can be colored the same in an edge coloring of $G$. This means that the edge chromatic number of any graph will be $\Delta(G)$ or $\Delta(G) + 1,$ where $\Delta(G)$ is the maximum degree of any vertex in $G.$

For the given graph $\Delta(G) = 5.$ If we try with $5$ colors we get an edge coloring as shown and so the edge chromatic number of graph $G$ is $\chi^{'}(G) = 5.$

Comments

Theorem 1.7. [3] Let G = Kn, the complete graph on n vertices, n ≥ 2.

Then edge chromatic number of (G) =  

∆(G) if n is even

∆(G) + 1 if n is odd

Taken from:

https://arxiv.org/pdf/1404.1698.pdf#:~:text=Definition%201.4.,for%20every%20nonempty%20graph%20G.&text=We%20denote%20the%20chromatic%20number,is%20denoted%20by%20%C2%AFG

.