A refinement of choosability of graphs

DOI10.1016/J.JCTB.2019.07.006MaRDI QIDQ2284741zbMATH OpenOpenAlexFDO

Publication date 15 January 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.08587

\(\lambda\)-assignment \(\lambda\)-choosability generalized signed graph planar graphs signed graph

Combinatorial aspects of partitions of integers (05A17) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Signed and weighted graphs (05C22)

Abstract: Assume

k

is a positive integer,

l a m b d a = k_{1}, k_{2}, l d o t s, k_{q}

is a partition of

k

and

G

is a graph. A

l a m b d a

-list assignment of

G

is a

k

-list assignment

L

of

G

such that the colour set

c u p_{v i n V (G)} L (v)

can be partitioned into

q

subsets

C_{1} c u p C_{2} l d o t s c u p C_{q}

and for each vertex

v

of

G

,

| L (v) c a p C_{i} | g e k_{i}

. We say

G

is

l a m b d a

-choosable if for each

l a m b d a

-list assignment

L

of

G

,

G

is

L

-colourable. It follows from the definition that if

l a m b d a = k

, then

l a m b d a

-choosable is the same as

k

-choosable, if

l a m b d a = 1, 1, l d o t s, 1

, then

l a m b d a

-choosable is equivalent to

k

-colourable. For the other partitions of

k

sandwiched between

k

and

1, 1, l d o t s, 1

in terms of refinements,

l a m b d a

-choosability reveals a complex hierarchy of colourability of graphs. We prove that for two partitions

l a m b d a, l a m b d a^{'}

of

k

, every

l a m b d a

-choosable graph is

l a m b d a^{'}

-choosable if and only if

l a m b d a^{'}

is a refinement of

l a m b d a

. Then we concentrate on

l a m b d a

-choosability of planar graphs for partitions

l a m b d a

of

4

. Several conjectures concerning colouring of generalized signed planar graphs are proposed and relations between these conjectures and list colouring conjectures for planar graphs are explored. In particular, it is proved that a conjecture of K"{u}ndgen and Ramamurthi on list colouring of planar graphs is implied by the conjecture that every planar graph is

2, 2

-choosable, and also implied by the conjecture of M'{a}v{c}ajov'{a}, Raspaud and v{S}koviera which asserts that every planar graph is signed MRS-

4

-colourable, and that a conjecture of Kang and Steffen asserting that every planar graph is signed KS-

4

-colourable implies that every planar graph is

1, 1, 2

-choosable.

Recommendations

Cites work

Cited in

(33)

This page was built for publication: A refinement of choosability of graphs

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