@inproceedings{4a22bb0c3a0645e89c4ffe5c917f71a1,

title = "H-colorings of large degree graphs",

abstract = "We consider the H-coloring problem on graphs with vertices of large degree. We prove that for H an odd cycle, the problem belongs to P. We also study the phase transition of the problem, for an infinite family of graphs of a given chromatic number, i.e. the threshold density value for which the problem changes from P to NP-complete. We extend the result for the case that the input graph has a logarithmic size of small degree vertices. As a corollary, we get a new result on the chromatic number; a new family of graphs, for which computing the chromatic number can be done in polynomial time.",

author = "Josep D{\'i}az and Jaroslav Neset{\v r}il and Maria Serna and Thilikos, {Dimitrios M.}",

year = "2002",

doi = "10.1007/3-540-36087-5_98",

language = "English (US)",

isbn = "3540000283",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "850--857",

editor = "Hassan Shafazand and Tjoa, {A. Min} and Hassan Shafazand",

booktitle = "EurAsia-ICT 2002",

note = "1st EurAsian Conference on Advances in Information and Communication Technology, EurAsia-ICT 2002 ; Conference date: 29-10-2002 Through 31-10-2002",

}