TY - JOUR

T1 - Some criteria for a graph to be Class 1

AU - Akbari, S.

AU - Cariolaro, D.

AU - Chavooshi, M.

AU - Ghanbari, M.

AU - Zare, S.

N1 - Funding Information:
The authors would like express their deep gratitude to the referees for their constructive and fruitful comments. The first, fourth, and last authors are indebted to the School of Mathematics, Institute for Research in Fundamental Sciences (IPM) for support. The research of the first author was in part supported by a grant from IPM (No. 90050212 ).

PY - 2012/9/6

Y1 - 2012/9/6

N2 - Let G be a graph. The core of G, denoted by GΔ, is the subgraph of G induced by the vertices of degree Δ(G), where Δ(G) is the maximum degree of G. A k-edge coloring of a graph G is a function f:E(G)L, where |L|=k and f(e1)≠f(e2), for every two adjacent edges e1,e2 of G. The edge chromatic number of G, denoted by χ′(G), is the minimum number k for which G has a k-edge coloring. A graph G is said to be Class 1 if χ′(G)= Δ(G) and Class 2 if χ′(G)=Δ(G)+1. In this paper, it is shown that, for every connected graph of even order, if GΔ=C6, then G is Class 1. Also, we prove that, if G is a connected graph, and every connected component of GΔ is a unicyclic graph or a tree, and GΔ is not a disjoint union of cycles, then G is Class 1.

AB - Let G be a graph. The core of G, denoted by GΔ, is the subgraph of G induced by the vertices of degree Δ(G), where Δ(G) is the maximum degree of G. A k-edge coloring of a graph G is a function f:E(G)L, where |L|=k and f(e1)≠f(e2), for every two adjacent edges e1,e2 of G. The edge chromatic number of G, denoted by χ′(G), is the minimum number k for which G has a k-edge coloring. A graph G is said to be Class 1 if χ′(G)= Δ(G) and Class 2 if χ′(G)=Δ(G)+1. In this paper, it is shown that, for every connected graph of even order, if GΔ=C6, then G is Class 1. Also, we prove that, if G is a connected graph, and every connected component of GΔ is a unicyclic graph or a tree, and GΔ is not a disjoint union of cycles, then G is Class 1.

KW - Class 1

KW - Core

KW - Edge coloring

KW - Unicyclic

UR - http://www.scopus.com/inward/record.url?scp=84862661944&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2011.09.035

DO - 10.1016/j.disc.2011.09.035

M3 - Article

AN - SCOPUS:84862661944

SN - 0012-365X

VL - 312

SP - 2593

EP - 2598

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 17

ER -