DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kim, Seog-Jin | ko |
dc.contributor.author | Lee, Sang June | ko |
dc.contributor.author | Park, Won-Jin | ko |
dc.date.accessioned | 2013-08-14T01:08:21Z | - |
dc.date.available | 2013-08-14T01:08:21Z | - |
dc.date.created | 2013-08-09 | - |
dc.date.created | 2013-08-09 | - |
dc.date.issued | 2013-09 | - |
dc.identifier.citation | DISCRETE APPLIED MATHEMATICS, v.161, no.13-14, pp.2207 - 2212 | - |
dc.identifier.issn | 0166-218X | - |
dc.identifier.uri | http://hdl.handle.net/10203/175006 | - |
dc.description.abstract | A dynamic coloring of a graph G is a proper coloring of the vertex set V (G) such that for each vertex of degree at least 2, its neighbors receive at least two distinct colors. The dynamic chromatic number chi(d)(G) of a graph G is the least number k such that G has a dynamic coloring with k colors. We show that chi(d)(G) <= 4 for every planar graph except C-5, which was conjectured in Chen et al. (2012)[5]. The list dynamic chromatic number ch(d)(G) of G is the least number k such that for any assignment of k-element lists to the vertices of G, there is a dynamic coloring of G where the color on each vertex is chosen from its list. Based on Thomassen's (1994) result [141 that every planar graph is 5-choosable, an interesting question is whether the list dynamic chromatic number of every planar graph is at most 5 or not. We answer this question by showing that chd(G) <= 5 for every planar graph. (C) 2013 Elsevier B.V. All rights reserved. | - |
dc.language | English | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.subject | MAP | - |
dc.title | Dynamic coloring and list dynamic coloring of planar graphs | - |
dc.type | Article | - |
dc.identifier.wosid | 000320680400043 | - |
dc.identifier.scopusid | 2-s2.0-84878287389 | - |
dc.type.rims | ART | - |
dc.citation.volume | 161 | - |
dc.citation.issue | 13-14 | - |
dc.citation.beginningpage | 2207 | - |
dc.citation.endingpage | 2212 | - |
dc.citation.publicationname | DISCRETE APPLIED MATHEMATICS | - |
dc.identifier.doi | 10.1016/j.dam.2013.03.005 | - |
dc.contributor.nonIdAuthor | Kim, Seog-Jin | - |
dc.contributor.nonIdAuthor | Park, Won-Jin | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Dynamic coloring | - |
dc.subject.keywordAuthor | Dynamic chromatic number | - |
dc.subject.keywordAuthor | Planar graph | - |
dc.subject.keywordAuthor | Four color theorem | - |
dc.subject.keywordPlus | MAP | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.