H-colorings of large degree graphs

Josep Díaz; Jaroslav Nesetřil; Maria Serna; Dimitrios M. Thilikos

doi:10.1007/3-540-36087-5_98

H-colorings of large degree graphs

Josep Díaz, Jaroslav Nesetřil, Maria Serna, Dimitrios M. Thilikos

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English (US)
Title of host publication	EurAsia-ICT 2002
Subtitle of host publication	Information and Communication Technology - First EurAsian Conference, Proceedings
Editors	Hassan Shafazand, A. Min Tjoa, Hassan Shafazand
Publisher	Springer Verlag
Pages	850-857
Number of pages	8
ISBN (Print)	3540000283, 9783540000280
DOIs	https://doi.org/10.1007/3-540-36087-5_98
State	Published - 2002
Event	1st EurAsian Conference on Advances in Information and Communication Technology, EurAsia-ICT 2002 - Shiraz, Iran, Islamic Republic of Duration: Oct 29 2002 → Oct 31 2002

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	2510 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	1st EurAsian Conference on Advances in Information and Communication Technology, EurAsia-ICT 2002
Country/Territory	Iran, Islamic Republic of
City	Shiraz
Period	10/29/02 → 10/31/02

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-36087-5_98

Cite this

Díaz, J., Nesetřil, J., Serna, M., & Thilikos, D. M. (2002). H-colorings of large degree graphs. In H. Shafazand, A. M. Tjoa, & H. Shafazand (Eds.), EurAsia-ICT 2002: Information and Communication Technology - First EurAsian Conference, Proceedings (pp. 850-857). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2510 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-36087-5_98

H-colorings of large degree graphs. / Díaz, Josep; Nesetřil, Jaroslav; Serna, Maria et al.
EurAsia-ICT 2002: Information and Communication Technology - First EurAsian Conference, Proceedings. ed. / Hassan Shafazand; A. Min Tjoa; Hassan Shafazand. Springer Verlag, 2002. p. 850-857 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2510 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Díaz, J, Nesetřil, J, Serna, M & Thilikos, DM 2002, H-colorings of large degree graphs. in H Shafazand, AM Tjoa & H Shafazand (eds), EurAsia-ICT 2002: Information and Communication Technology - First EurAsian Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2510 LNCS, Springer Verlag, pp. 850-857, 1st EurAsian Conference on Advances in Information and Communication Technology, EurAsia-ICT 2002, Shiraz, Iran, Islamic Republic of, 10/29/02. https://doi.org/10.1007/3-540-36087-5_98

Díaz J, Nesetřil J, Serna M, Thilikos DM. H-colorings of large degree graphs. In Shafazand H, Tjoa AM, Shafazand H, editors, EurAsia-ICT 2002: Information and Communication Technology - First EurAsian Conference, Proceedings. Springer Verlag. 2002. p. 850-857. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-36087-5_98

Díaz, Josep ; Nesetřil, Jaroslav ; Serna, Maria et al. / H-colorings of large degree graphs. EurAsia-ICT 2002: Information and Communication Technology - First EurAsian Conference, Proceedings. editor / Hassan Shafazand ; A. Min Tjoa ; Hassan Shafazand. Springer Verlag, 2002. pp. 850-857 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

}

TY - GEN

T1 - H-colorings of large degree graphs

AU - Díaz, Josep

AU - Nesetřil, Jaroslav

AU - Serna, Maria

AU - Thilikos, Dimitrios M.

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84855376051&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84855376051&partnerID=8YFLogxK

U2 - 10.1007/3-540-36087-5_98

DO - 10.1007/3-540-36087-5_98

M3 - Conference contribution

AN - SCOPUS:84855376051

SN - 3540000283

SN - 9783540000280

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 850

EP - 857

BT - EurAsia-ICT 2002

A2 - Shafazand, Hassan

A2 - Tjoa, A. Min

A2 - Shafazand, Hassan

PB - Springer Verlag

T2 - 1st EurAsian Conference on Advances in Information and Communication Technology, EurAsia-ICT 2002

Y2 - 29 October 2002 through 31 October 2002

ER -

H-colorings of large degree graphs

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this