Girth and λ \lambda ‐choosability of graphs

DOI10.1002/JGT.22931MaRDI QIDQ6074593zbMATH OpenOpenAlexFDO

Authors Yangyan Gu, Xuding Zhu

Publication date 12 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

girthpartition refinementinteger partitionlist colouring\(\lambda\)-choosability

Mathematics Subject Classification ID

Combinatorial aspects of partitions of integers (05A17) Coloring of graphs and hypergraphs (05C15)

Abstract: Assume $k$ is a positive integer, $lambda=k_1,k_2,\mathrm{...},k_q$ is a partition of $k$ and $G$ is a graph. A $lambda$-assignment of $G$ is a $k$-assignment $L$ of $G$ such that the colour set $$ can be partitioned into $q$ subsets $C_{1}cup{C}_{2}cupcdotscup{C}_q$ and for each vertex $v$ of $G$, $|L(v)cap{C}_i|=k_i$. We say $G$ is $lambda$-choosable if for each $lambda$-assignment $L$ of $G$, $G$ is $L$-colourable. In particular, if $lambda=k$, then $lambda$-choosable is the same as $k$-choosable, if $lambda=1,1,\mathrm{...},1$, then $lambda$-choosable is equivalent to $k$-colourable. For the other partitions of $k$ sandwiched between $k$ and $1,1,\mathrm{...},1$ in terms of refinements, $lambda$-choosability reveals a complex hierarchy of colourability of graphs. Assume $lambda=k_1,ldots,k_q$ is a partition of $k$ and $lambd{a}^{\prime }$ is a partition of $k^{\prime }gek$. We write $lambdalelambd{a}^{\prime }$ if there is a partition $lambd{a}^{″}=k^{\prime }{\text{'}}_1,ldots,k^{\prime }{\text{'}}_q$ of $k^{\prime }$ with $k^{\prime }{\text{'}}_{i}ge{k}_i$ for $i=1,2,ldots,q$ and $lambd{a}^{\prime }$ is a refinement of $lambd{a}^{″}$. It follows from the definition that if $lambdalelambd{a}^{\prime }$, then every $lambda$-choosable graph is $lambd{a}^{\prime }$-choosable. It was proved in [X. Zhu, A refinement of choosability of graphs, J. Combin. Theory, Ser. B 141 (2020) 143 - 164] that the converse is also true. This paper strengthens this result and proves that for any $lambdaotlelambd{a}^{\prime }$, for any integer $g$, there exists a graph of girth at least $g$ which is $lambda$-choosable but not $lambd{a}^{\prime }$-choosable.

Recommendations

• A refinement of choosability of graphs
• On generalized list colourings of graphs
• Chromatic λ‐choosable and λ‐paintable graphs
• The 3-choosability of plane graphs without 3-,6-,9-and 10-cycles
• Refined List Version of Hadwiger’s Conjecture

Cites work

• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 927067 (Why is no real title available?)
• A refinement of choosability of graphs
• Coloring, sparseness and girth
• Graph Theory and Probability
• On sparse graphs with given colorings and homomorphisms.
• Properties of Descartes' Construction of Triangle-Free Graphs with High Chromatic Number

Cited in

(5)

• Circular choosability of planar graphs with large girth.
• (\(1,\lambda\))-embedded graphs and the acyclic edge choosability
• A refinement of choosability of graphs
• The \(b\)-continuity of graphs with large girth
• Refined List Version of Hadwiger’s Conjecture

This page was built for publication: Girth and λ $\lambda $‐choosability of graphs

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