# Coloring Graph Problem

If G is a graph containing no loops or multiple edges, then the edge-chromatic number $X_e(C)$ of G is defined to be the least number of colours needed to colour the edges of G in such a way that no two adjacent edges have the same colour.

How to find edge-chromatic number :

1)Complete Graph($K_n$)

[I know $k_n$ is (n-1)regular and if n is even then edge-chromatic number of $k_n$ is n-1 and if n is odd then edge-chromatic number of $k_n$ is n,but how to prove it??]

2)Wheel($W_n$)

-

3
– joriki Nov 1 '12 at 9:22

1
Also, it seems unlikely that you don't have at least some rudimentary thoughts of your own on at least part 4) of the problem -- answers will be much more useful if you point out specifically what you already understand and what's causing you trouble. – joriki Nov 1 '12 at 9:26

## 1 Answer

For a complete graph with an even number of vertices, this amounts to finding a 1-factorisation, such as the following:

A general construction is formed by rotating a "starter", such as the following:

Each rotation describes where to place the edges of a single colour. Picture source:

Mendelsohn and Rosa, One-factorizations of the complete graph—A survey, Journal of Graph Theory 9 (1985) 43–65. (link)

See also the above reference for further details on how to construct 1-factorisations of $K_{2n}$ and near 1-factorisations of $K_{2n-1}$. Hence

Observation: The edge-chromatic number of $K_{2n}$ is $2n-1$ (its maximum degree) for $n \geq 1$.

For $K_{2n-1}$, we simply start with a 1-factorisation of $K_{2n}$ and delete a vertex, which results in $2n-1$ distinct edge colours. This is the best possible, since each edge colour can occur at most $n-1$ times (without having adjacent monochromatic edges), so we need at least $$\frac{{2n-1} \choose 2}{n-1}=2n-1$$ colours.

Observation: The edge-chromatic number of $K_{2n-1}$ is $2n-1$ for $n \geq 2$.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 18, "mathjax_display_tex": 1, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9220823645591736, "perplexity_flag": "head"}