Equitable colorings of outerplanar graphs

A. V. Kostochka

doi:10.1016/S0012-365X(02)00538-1

Equitable colorings of outerplanar graphs

A. V. Kostochka

Mathematics

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

Abstract

A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most 1. In this note, we prove the conjecture of Yap and Zhang that every outerplanar graph with maximum degree at most Δ admits an equitable k-coloring for every k ≥ 1 + Δ/2. This restriction on k cannot be weakened.

Original language	English (US)
Pages (from-to)	X373-377
Journal	Discrete Mathematics
Volume	258
Issue number	1-3
DOIs	https://doi.org/10.1016/S0012-365X(02)00538-1
State	Published - Dec 6 2002

Keywords

Equitable coloring
Graph coloring
Outerplanar graphs

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Online availability

10.1016/S0012-365X(02)00538-1

Library availability

Discover UIUC Full Text

Cite this

@article{0a33e6d21ec740568f1cefc21a43e788,

title = "Equitable colorings of outerplanar graphs",

abstract = "A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most 1. In this note, we prove the conjecture of Yap and Zhang that every outerplanar graph with maximum degree at most Δ admits an equitable k-coloring for every k ≥ 1 + Δ/2. This restriction on k cannot be weakened.",

keywords = "Equitable coloring, Graph coloring, Outerplanar graphs",

author = "Kostochka, {A. V.}",

note = "Funding Information: ∗Corresponding author. Department of Mathematics, University of Illinois, Urbana-Champaign, 1409 W. Green Street, Urbana, IL 61801, USA. Tel.: +217-265-8037. E-mail address: kostochk@math.uiuc.edu (A.V. Kostochka). 1This work was partially supported by the Grants 99-01-00581 and 97-01-01075 of the RFFR and by the Grant Intas-Open-97-1001.",

year = "2002",

month = dec,

day = "6",

doi = "10.1016/S0012-365X(02)00538-1",

language = "English (US)",

volume = "258",

pages = "X373--377",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier",

number = "1-3",

}

TY - JOUR

T1 - Equitable colorings of outerplanar graphs

AU - Kostochka, A. V.

N1 - Funding Information: ∗Corresponding author. Department of Mathematics, University of Illinois, Urbana-Champaign, 1409 W. Green Street, Urbana, IL 61801, USA. Tel.: +217-265-8037. E-mail address: kostochk@math.uiuc.edu (A.V. Kostochka). 1This work was partially supported by the Grants 99-01-00581 and 97-01-01075 of the RFFR and by the Grant Intas-Open-97-1001.

PY - 2002/12/6

Y1 - 2002/12/6

N2 - A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most 1. In this note, we prove the conjecture of Yap and Zhang that every outerplanar graph with maximum degree at most Δ admits an equitable k-coloring for every k ≥ 1 + Δ/2. This restriction on k cannot be weakened.

AB - A proper vertex coloring of a graph is equitable if the sizes of color classes differ by at most 1. In this note, we prove the conjecture of Yap and Zhang that every outerplanar graph with maximum degree at most Δ admits an equitable k-coloring for every k ≥ 1 + Δ/2. This restriction on k cannot be weakened.

KW - Equitable coloring

KW - Graph coloring

KW - Outerplanar graphs

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

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

U2 - 10.1016/S0012-365X(02)00538-1

DO - 10.1016/S0012-365X(02)00538-1

M3 - Article

AN - SCOPUS:0037032962

SN - 0012-365X

VL - 258

SP - X373-377

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1-3

ER -

Equitable colorings of outerplanar graphs

Abstract

Keywords

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this