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

From MaRDI portal

(Redirected from Publication:490305)

Jump to:navigation, search

MaRDI QIDQ490305zbMATH OpenFDO

Authors Fei-Huang Chang, Hongbin Chen, Junyi Guo, Yu-Pei Huang

Publication date 22 January 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.2700, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p6

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Ohba's conjecture online list coloring paintability

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Games on graphs (graph-theoretic aspects) (05C57) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: This paper studies the on-line choice number on 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

k_{1} - s u m_{p = 2}^{m} (f r a c p^{2} 2 - f r a c 3 p 2 + 1) k_{p} g e q 0

, where

k_{p}

denotes the number of parts of cardinality

p

, then

G

is on-line chromatic-choosable. (2) If

| V (G) | l e q f r a c m^{2} - m + 2 m^{2} - 3 m + 4 c h i (G)

, then

G

is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs

K_{m s t a r k}

is at most

(m + f r a c 12 - s q r t 2 m - 2) k

for

m g e q 3

.

Summary: This paper studies the on-line choice number on 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 \(k_1-\sum_{p=2}^m\left(\frac{p^2}{2}-\frac{3p}{2}+1\right)k_p\geqslant 0\), where \(k_p\) denotes the number of parts of cardinality \(p\), then \(G\) is on-line chromatic-choosable. (2) If \(|V(G)|\leq\frac{m^2-m+2}{m^2-3m+4}\chi(G)\), then \(G\) is on-line chromatic-choosable. (3) The on-line choice number of regular complete multipartite graphs \(K_{m\star k}\) is at most \(\left(m+\frac{1}{2}-\sqrt{2m-2}\right)k\) for \(m\geq 3\).

Recommendations

Cites work

Cited in

(3)

This page was built for publication: On-line choice number of complete multipartite graphs: an algorithmic approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490305)

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=On-line_choice_number_of_complete_multipartite_graphs:_an_algorithmic_approach&oldid=62228826"