On-line choice number of complete multipartite graphs: An algorithmic approach

Fei Huang Chang; Jun Yi Guo; Hong Bin Chen; Yu Pei Huang

doi:10.37236/3378

On-line choice number of complete multipartite graphs: An algorithmic approach

Fei Huang Chang^*, Jun Yi Guo, Hong Bin Chen, Yu Pei Huang

^*Corresponding author for this work

Department of Mathematics

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

Abstract

This paper studies the on-line choice number of complete multipartite graphs with independence number m. We give a unified strategy for every prescribed m.Our main result leads to several interesting consequences comparable to known results. (1) If (Formula Presented)where kp denotes the number of parts of cardinality p, then G is on-line chromatic-choosable. (2) If (Formula Presented)then G is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs Km*k is at most k for (Formula Presented).

Original language	English
Journal	Electronic Journal of Combinatorics
Volume	22
Issue number	1
DOIs	https://doi.org/10.37236/3378
Publication status	Published - 2015 Jan 2

Keywords

Ohba’s conjecture
On-line list coloring

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Applied Mathematics

Access to Document

10.37236/3378

Cite this

@article{4fa3ae69a05349c8b16afe6aa2e95c23,

title = "On-line choice number of complete multipartite graphs: An algorithmic approach",

abstract = "This paper studies the on-line choice number of complete multipartite graphs with independence number m. We give a unified strategy for every prescribed m.Our main result leads to several interesting consequences comparable to known results. (1) If (Formula Presented)where kp denotes the number of parts of cardinality p, then G is on-line chromatic-choosable. (2) If (Formula Presented)then G is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs Km*k is at most k for (Formula Presented).",

keywords = "Ohba{\textquoteright}s conjecture, On-line list coloring",

author = "Chang, {Fei Huang} and Guo, {Jun Yi} and Chen, {Hong Bin} and Huang, {Yu Pei}",

year = "2015",

month = jan,

day = "2",

doi = "10.37236/3378",

language = "English",

volume = "22",

journal = "Electronic Journal of Combinatorics",

issn = "1077-8926",

publisher = "Electronic Journal of Combinatorics",

number = "1",

}

TY - JOUR

T1 - On-line choice number of complete multipartite graphs

T2 - An algorithmic approach

AU - Chang, Fei Huang

AU - Guo, Jun Yi

AU - Chen, Hong Bin

AU - Huang, Yu Pei

PY - 2015/1/2

Y1 - 2015/1/2

N2 - This paper studies the on-line choice number of complete multipartite graphs with independence number m. We give a unified strategy for every prescribed m.Our main result leads to several interesting consequences comparable to known results. (1) If (Formula Presented)where kp denotes the number of parts of cardinality p, then G is on-line chromatic-choosable. (2) If (Formula Presented)then G is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs Km*k is at most k for (Formula Presented).

AB - This paper studies the on-line choice number of complete multipartite graphs with independence number m. We give a unified strategy for every prescribed m.Our main result leads to several interesting consequences comparable to known results. (1) If (Formula Presented)where kp denotes the number of parts of cardinality p, then G is on-line chromatic-choosable. (2) If (Formula Presented)then G is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs Km*k is at most k for (Formula Presented).

KW - Ohba’s conjecture

KW - On-line list coloring

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

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

U2 - 10.37236/3378

DO - 10.37236/3378

M3 - Article

AN - SCOPUS:84920272228

SN - 1077-8926

VL - 22

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

ER -

On-line choice number of complete multipartite graphs: An algorithmic approach

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this