Back to Search Start Over

The Chromatic Index of a Graph Whose Core has Maximum Degree $2$

Authors :
M. Ghanbari
Saieed Akbari
Mikio Kano
Mohammad Javad Nikmehr
Source :
The Electronic Journal of Combinatorics. 19
Publication Year :
2012
Publisher :
The Electronic Journal of Combinatorics, 2012.

Abstract

Let $G$ be a graph. The core of $G$, denoted by $G_{\Delta}$, is the subgraph of $G$ induced by the vertices of degree $\Delta(G)$, where $\Delta(G)$ denotes the maximum degree of $G$. A $k$-edge coloring of $G$ is a function $f:E(G)\rightarrow L$ such that $|L| = k$ and $f(e_1)\neq f(e_2)$ for all two adjacent edges $e_1$ and $e_2$ of $G$. The chromatic index of $G$, denoted by $\chi'(G)$, is the minimum number $k$ for which $G$ has a $k$-edge coloring. A graph $G$ is said to be Class $1$ if $\chi'(G) = \Delta(G)$ and Class $2$ if $\chi'(G) = \Delta(G) + 1$. In this paper it is shown that every connected graph $G$ of even order and with $\Delta(G_{\Delta})\leq 2$ is Class $1$ if $|G_{\Delta}|\leq 9$ or $G_{\Delta}$ is a cycle of order $10$.

Details

ISSN :
10778926
Volume :
19
Database :
OpenAIRE
Journal :
The Electronic Journal of Combinatorics
Accession number :
edsair.doi...........6ab3127b23706db8bd892ec3b442a031