Planar graphs decomposable into a forest and a matching

Oleg V. Borodin; Anna O. Ivanova; Alexandr V. Kostochka; Naeem N. Sheikh

doi:10.1016/j.disc.2007.12.104

Planar graphs decomposable into a forest and a matching

Oleg V. Borodin, Anna O. Ivanova, Alexandr V. Kostochka, Naeem N. Sheikh

Mathematics

Research output: Contribution to journal › Article › peer-review

Abstract

He, Hou, Lih, Shao, Wang, and Zhu showed that a planar graph of girth 11 can be decomposed into a forest and a matching. Borodin, Kostochka, Sheikh, and Yu improved the bound on girth to 9. We give sufficient conditions for a planar graph with 3-cycles to be decomposable into a forest and a matching.

Original language	English (US)
Pages (from-to)	277-279
Number of pages	3
Journal	Discrete Mathematics
Volume	309
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2007.12.104
State	Published - Jan 6 2009

Keywords

Edge decompositions
Graph decompositions
Planar graphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/j.disc.2007.12.104

Library availability

Discover UIUC Full Text

Cite this

@article{3dcf4231ce044578be777f84596c65fe,

title = "Planar graphs decomposable into a forest and a matching",

abstract = "He, Hou, Lih, Shao, Wang, and Zhu showed that a planar graph of girth 11 can be decomposed into a forest and a matching. Borodin, Kostochka, Sheikh, and Yu improved the bound on girth to 9. We give sufficient conditions for a planar graph with 3-cycles to be decomposable into a forest and a matching.",

keywords = "Edge decompositions, Graph decompositions, Planar graphs",

author = "Borodin, {Oleg V.} and Ivanova, {Anna O.} and Kostochka, {Alexandr V.} and Sheikh, {Naeem N.}",

note = "Funding Information: The first author{\textquoteright}s research was supported in part by RFBR grant 05-01-00816. The second author{\textquoteright}s research was supported in part by RFBR grant 06-01-00694. The third author{\textquoteright}s research was supported in part by the grant DMS-0650784. ",

year = "2009",

month = jan,

day = "6",

doi = "10.1016/j.disc.2007.12.104",

language = "English (US)",

volume = "309",

pages = "277--279",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Planar graphs decomposable into a forest and a matching

AU - Borodin, Oleg V.

AU - Ivanova, Anna O.

AU - Kostochka, Alexandr V.

AU - Sheikh, Naeem N.

N1 - Funding Information: The first author’s research was supported in part by RFBR grant 05-01-00816. The second author’s research was supported in part by RFBR grant 06-01-00694. The third author’s research was supported in part by the grant DMS-0650784.

PY - 2009/1/6

Y1 - 2009/1/6

N2 - He, Hou, Lih, Shao, Wang, and Zhu showed that a planar graph of girth 11 can be decomposed into a forest and a matching. Borodin, Kostochka, Sheikh, and Yu improved the bound on girth to 9. We give sufficient conditions for a planar graph with 3-cycles to be decomposable into a forest and a matching.

AB - He, Hou, Lih, Shao, Wang, and Zhu showed that a planar graph of girth 11 can be decomposed into a forest and a matching. Borodin, Kostochka, Sheikh, and Yu improved the bound on girth to 9. We give sufficient conditions for a planar graph with 3-cycles to be decomposable into a forest and a matching.

KW - Edge decompositions

KW - Graph decompositions

KW - Planar graphs

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

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

U2 - 10.1016/j.disc.2007.12.104

DO - 10.1016/j.disc.2007.12.104

M3 - Article

AN - SCOPUS:56349118997

SN - 0012-365X

VL - 309

SP - 277

EP - 279

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -

Planar graphs decomposable into a forest and a matching

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this