DC Field | Value | Language |
---|---|---|
dc.contributor.author | Choi, Ilkyoo | ko |
dc.contributor.author | Zhang, Haihui | ko |
dc.date.accessioned | 2015-01-27T02:37:13Z | - |
dc.date.available | 2015-01-27T02:37:13Z | - |
dc.date.created | 2014-09-30 | - |
dc.date.created | 2014-09-30 | - |
dc.date.issued | 2014-10 | - |
dc.identifier.citation | DISCRETE MATHEMATICS, v.333, pp.101 - 105 | - |
dc.identifier.issn | 0012-365X | - |
dc.identifier.uri | http://hdl.handle.net/10203/193141 | - |
dc.description.abstract | The vertex arboricity a(G) of a graph G is the minimum k such that V(G) can be partitioned into k sets where each set induces a forest. For a planar graph G, it is known that a(G) <= 3. In two recent papers, it was proved that planar graphs without k-cycles for some k E {3, 4, 5, 6, 7} have vertex arboricity at most 2. For a toroidal graph G, it is known that a(G) <= 4. Let us consider the following question: do toroidal graphs without k-cycles have vertex arboricity at most 2? It was known that the question is true for k = 3, and recently, Zhang proved the question is true for k = 5. Since a complete graph on 5 vertices is a toroidal graph without any k-cycles for k >= 6 and has vertex arboricity at least three, the only unknown case was k = 4. We solve this case in the affirmative; namely, we show that toroidal graphs without 4-cycles have vertex arboricity at most 2. | - |
dc.language | English | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.subject | POINT-ARBORICITY | - |
dc.subject | PLANAR GRAPHS | - |
dc.title | Vertex arboricity of toroidal graphs with a forbidden cycle | - |
dc.type | Article | - |
dc.identifier.wosid | 000341217300012 | - |
dc.identifier.scopusid | 2-s2.0-84903824012 | - |
dc.type.rims | ART | - |
dc.citation.volume | 333 | - |
dc.citation.beginningpage | 101 | - |
dc.citation.endingpage | 105 | - |
dc.citation.publicationname | DISCRETE MATHEMATICS | - |
dc.identifier.doi | 10.1016/j.disc.2014.06.011 | - |
dc.contributor.nonIdAuthor | Zhang, Haihui | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordPlus | POINT-ARBORICITY | - |
dc.subject.keywordPlus | PLANAR GRAPHS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.