Let $H$ be a nonempty regular graph of odd order and let $G$ be a graph obtained from $H$ by deleting $\frac{1}{2}(\Delta( H)-1 )$ or fewer edges. How to show that $G$ is of class two? a graph is of class two when$x_1(G)=\Delta(G)+1$ and belong class one when$x_1(G)=\Delta(G)$ . that $x_1(G)$ is a minimum colors need to color the edge of graph ,such that adjacent edge have a different color. Or the smallest number of colors needed in a (proper ,meaning no two adjacent edges are assigned the same color) edge coloring of $G$ is a chromatic index , or edge chromatic number or $x_1(G)$.
3
-
$\begingroup$ I know every regular graph of odd order is of class two, so H is of order two. I can't proof that G is of class two? $\endgroup$– yaodao vangMay 26, 2017 at 16:35
-
$\begingroup$ @ yaodao vang: Reading only the first two lines of this question, one wonders if $\frac12(\Delta(H)-1)$ is meant to suggest that $\Delta(H)$ is odd. It does not follow from what you wrote. (E.g. the complete graph $H$ on three vertices is non-empty, regular, of odd order, but has $\Delta(H)=2$, and hence $\frac12(\Delta(H)-1)$ non-integral.) Please, clarify whether $\Delta(H)$ is assumed to be odd. $\endgroup$– Peter HeinigMay 26, 2017 at 19:34
-
$\begingroup$ Also, please use the standard $\chi'(G)$ instead of $x_1(G)$ for the chromatic index. $\endgroup$– Peter HeinigMay 26, 2017 at 19:36
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
If order means a number $2k+1$ of vertices, we simply note that each color has at most $k$ edges, so $d=\Delta(H)$ colors have at most $dk$ edges, thus at least $d/2=|E|-dk$ edges must be removed from $H$ for getting a graph of class 1.
answered May 26, 2017 at 17:12