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 = "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 - 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 - https://www.scopus.com/pages/publications/56349118997

UR - https://www.scopus.com/pages/publications/56349118997#tab=citedBy

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