The chromatic index of a graph whose core has maximum degree 2

Mikio Kano¹ ; Saieed Akbari² ; Maryam Ghanbari³ ; Mohammad Javad Nikmehr⁴

¹Ibaraki University
²Sharif University of Technology and Institute for Research in Fundamental Sciences
³K. N. Toosi University of Technology and Institute for Research in Fundamental Sciences
⁴K. N. Toosi University of Technology

The electronic journal of combinatorics, Tome 19 (2012) no. 1

Résumé

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$.

Détail

DOI : 10.37236/2101

Classification : 05C15, 05C70, 05C07
Mots-clés : chromatic index, edge coloring, class 1, core of a graph