On structure of graphs embedded on surfaces of nonnegative characteristic with application to choosability

In this paper, we prove a structural theorem of Lebesgue's type concerning some unavoidable configurations for graphs which can be embedded on surfaces of nonnegative characteristic and in which no two 3-cycles share a common vertex. As a corollary, we get a result about choosability of graphs...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2002-04, Vol.248 (1), p.283-291
Main Author: Xu, Baogang
Format: Article
Language:English
Subjects:
3-cycle
Choosability
Embedded graph
Exact sciences and technology
Mathematics
Sciences and techniques of general use
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we prove a structural theorem of Lebesgue's type concerning some unavoidable configurations for graphs which can be embedded on surfaces of nonnegative characteristic and in which no two 3-cycles share a common vertex. As a corollary, we get a result about choosability of graphs embedded in surface of positive characteristic.
ISSN:0012-365X
1872-681X
DOI:10.1016/S0012-365X(01)00351-X