Premium
Circular chromatic number of subgraphs
Author(s) -
Hajiabolhassan Hossein,
Zhu Xuding
Publication year - 2003
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.10127
Subject(s) - combinatorics , mathematics , chromatic scale , graph , vertex (graph theory) , integer (computer science) , induced subgraph , discrete mathematics , computer science , programming language
This paper proves that every ( n + )‐chromatic graph contains a subgraph H with $\chi _c (H) = n$ . This provides an easy method for constructing sparse graphs G with $\chi_c (G) = \chi ( G) = n$ . It is also proved that for any ε > 0, for any fraction k/d > 2, there exists an integer g such that if G has girth at least g and $\chi _c (G) = k/d$ then for every vertex v of G , $\chi _c (G-{v})> k/d - \varepsilon $ . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 95–105, 2003
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom