Some criteria for a graph to be Class 1

S. Akbari, D. Cariolaro, M. Chavooshi, M. Ghanbari, S. Zare*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)

Abstract

Let G be a graph. The core of G, denoted by , 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 =C6, then G is Class 1. Also, we prove that, if G is a connected graph, and every connected component of is a unicyclic graph or a tree, and is not a disjoint union of cycles, then G is Class 1.

Original languageEnglish
Pages (from-to)2593-2598
Number of pages6
JournalDiscrete Mathematics
Volume312
Issue number17
DOIs
Publication statusPublished - 6 Sept 2012

Keywords

  • Class 1
  • Core
  • Edge coloring
  • Unicyclic

Fingerprint

Dive into the research topics of 'Some criteria for a graph to be Class 1'. Together they form a unique fingerprint.

Cite this