“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 2338
School of Mathematics
  Title:   Circular chromatic number of subgraphs
1.  H. Hajiabolhassan
2.  X. Zhu
  Status:   Published
  Journal: J. Graph Theory
  No.:  2
  Vol.:  44
  Year:  2003
  Pages:   95-105
  Supported by:  IPM
This paper proves that every (n + 1)-chromatic graph contains a subgraph H with χc (H) = n . This provides easy methods for constructing sparse graphs G with χc (G) = χ(G) = n. It is also proved that for any ε > 0, for any fraction k/d > 2, there exsits an integer g such that if G has girth at least g and χc (G) = k / d then for every vertex υ of G, χc(G− υ) > k / d − ϵ. This implies that G has an induced subgraph H with χc(G) − ϵ < χc (H) < χc(G).

Download TeX format
back to top
scroll left or right