DC Field | Value | Language |
---|---|---|
dc.contributor.author | Choi, Ilkyoo | ko |
dc.date.accessioned | 2017-05-15T05:17:25Z | - |
dc.date.available | 2017-05-15T05:17:25Z | - |
dc.date.created | 2017-05-08 | - |
dc.date.created | 2017-05-08 | - |
dc.date.issued | 2017-05 | - |
dc.identifier.citation | JOURNAL OF GRAPH THEORY, v.85, no.1, pp.172 - 186 | - |
dc.identifier.issn | 0364-9024 | - |
dc.identifier.uri | http://hdl.handle.net/10203/223652 | - |
dc.description.abstract | The choosability (G) of a graph G is the minimum k such that having k colors available at each vertex guarantees a proper coloring. Given a toroidal graph G, it is known that (G)7, and (G)=7 if and only if G contains K-7. Cai etal. (J Graph Theory 65(1) (2010), 1-15) proved that a toroidal graph G without 7-cycles is 6-choosable, and (G)=6 if and only if G contains K-6. They also proved that a toroidal graph G without 6-cycles is 5-choosable, and conjectured that (G)=5 if and only if G contains K-5. We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither K-5 nor cycles of length at least 6; moreover, this family of graphs is embeddable on every surface except the plane and the projective plane. Instead, we prove the following slightly weaker statement suggested by Zhu: toroidal graphs containing neither <mml:msubsup>K5-</mml:msubsup> (a K-5 missing one edge) nor 6-cycles are 4-choosable. This is sharp in the sense that forbidding only one of the two structures does not ensure that the graph is 4-choosable. (C) 2016 Wiley Periodicals, Inc. | - |
dc.language | English | - |
dc.publisher | WILEY-BLACKWELL | - |
dc.subject | PLANAR GRAPHS | - |
dc.subject | CHOOSABILITY | - |
dc.subject | COLORINGS | - |
dc.subject | CYCLES | - |
dc.title | Toroidal graphs containing neither K-5(-) nor 6-cycles are 4-choosable | - |
dc.type | Article | - |
dc.identifier.wosid | 000399293700012 | - |
dc.identifier.scopusid | 2-s2.0-84971473583 | - |
dc.type.rims | ART | - |
dc.citation.volume | 85 | - |
dc.citation.issue | 1 | - |
dc.citation.beginningpage | 172 | - |
dc.citation.endingpage | 186 | - |
dc.citation.publicationname | JOURNAL OF GRAPH THEORY | - |
dc.identifier.doi | 10.1002/jgt.22054 | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | choosability | - |
dc.subject.keywordAuthor | toroidal graph | - |
dc.subject.keywordAuthor | discharging | - |
dc.subject.keywordPlus | PLANAR GRAPHS | - |
dc.subject.keywordPlus | CHOOSABILITY | - |
dc.subject.keywordPlus | COLORINGS | - |
dc.subject.keywordPlus | CYCLES | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.