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 -