The equitable chromatic threshold of the Cartesian product of bipartite graphs is at most 4

Zhidan Yan; Wu-Hsiung Lin; Wei Wang

doi:10.11650/tjm.18.2014.3645

The equitable chromatic threshold of the Cartesian product of bipartite graphs is at most 4

Zhidan Yan, Wu-Hsiung Lin^*, Wei Wang

^*Corresponding author for this work

Department of Applied Mathematics

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

2 Scopus citations

Abstract

A graph G is equitably k-colorable if its vertex set can be partitioned into k independent sets, any two of which differ in size by at most 1. We prove a conjecture of Lin and Chang which asserts that for any bipartite graphs G and H, their Cartesian product GH is equitably k-colorable whenever k ≥ 4.

Original language	English
Pages (from-to)	773-780
Number of pages	8
Journal	Taiwanese Journal of Mathematics
Volume	18
Issue number	3
DOIs	https://doi.org/10.11650/tjm.18.2014.3645
State	Published - 1 Jan 2014

Keywords

Bipartite graph
Cartesian product
Equitable chromatic threshold
Equitable coloring

Access to Document

10.11650/tjm.18.2014.3645

Fingerprint Dive into the research topics of 'The equitable chromatic threshold of the Cartesian product of bipartite graphs is at most 4'. Together they form a unique fingerprint.

Cite this

@article{3bcd4bd82f4940d7bd03aeb12916ac1e,

title = "The equitable chromatic threshold of the Cartesian product of bipartite graphs is at most 4",

abstract = "A graph G is equitably k-colorable if its vertex set can be partitioned into k independent sets, any two of which differ in size by at most 1. We prove a conjecture of Lin and Chang which asserts that for any bipartite graphs G and H, their Cartesian product GH is equitably k-colorable whenever k ≥ 4.",

keywords = "Bipartite graph, Cartesian product, Equitable chromatic threshold, Equitable coloring",

author = "Zhidan Yan and Wu-Hsiung Lin and Wei Wang",

year = "2014",

month = jan,

day = "1",

doi = "10.11650/tjm.18.2014.3645",

language = "English",

volume = "18",

pages = "773--780",

journal = "Taiwanese Journal of Mathematics",

issn = "1027-5487",

publisher = "Mathematical Society of the Rep. of China",

number = "3",

}

TY - JOUR

T1 - The equitable chromatic threshold of the Cartesian product of bipartite graphs is at most 4

AU - Yan, Zhidan

AU - Lin, Wu-Hsiung

AU - Wang, Wei

PY - 2014/1/1

Y1 - 2014/1/1

N2 - A graph G is equitably k-colorable if its vertex set can be partitioned into k independent sets, any two of which differ in size by at most 1. We prove a conjecture of Lin and Chang which asserts that for any bipartite graphs G and H, their Cartesian product GH is equitably k-colorable whenever k ≥ 4.

AB - A graph G is equitably k-colorable if its vertex set can be partitioned into k independent sets, any two of which differ in size by at most 1. We prove a conjecture of Lin and Chang which asserts that for any bipartite graphs G and H, their Cartesian product GH is equitably k-colorable whenever k ≥ 4.

KW - Bipartite graph

KW - Cartesian product

KW - Equitable chromatic threshold

KW - Equitable coloring

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

U2 - 10.11650/tjm.18.2014.3645

DO - 10.11650/tjm.18.2014.3645

M3 - Article

AN - SCOPUS:84901633813

VL - 18

SP - 773

EP - 780

JO - Taiwanese Journal of Mathematics

JF - Taiwanese Journal of Mathematics

SN - 1027-5487

IS - 3

ER -

The equitable chromatic threshold of the Cartesian product of bipartite graphs is at most 4

Abstract

Keywords

Access to Document

Other files and links

Cite this