ISSN 1234-3099 (print version)
ISSN 2083-5892 (electronic version)
SCImago Journal Rank (SJR) 2018: 0.763
Rejection Rate (2017-2018): c. 84%
Discussiones Mathematicae Graph Theory 33(1) (2013)
Dedicated to Mietek Borowiecki on the occasion of his seventieth birthday
Alfréd Rényi Institute of Mathematics
Hungarian Academy of Sciences
H-1053 Budapest, Reáltanoda u. 13-15, Hungary
Department of Computer Science and Systems Technology
University of Pannonia
H-8200 Veszprém, Egyetem u. 10, Hungary
In this note we initiate the study of graphs in which the
choice number equals the clique number or the chromatic
number in every induced subgraph.
We call them choice-ω-perfect and choice-χ-perfect graphs, respectively.
The main result of the paper states that the square of every cycle
Keywords: graph coloring, list coloring, choice-perfect graph
2010 Mathematics Subject Classification: 05C15, 05C17, 05C75.
Received 28 April 2012 Revised 5 September 2012 Accepted 5 September 2012