List coloring a Cartesian product with a complete bipartite factor

DOI10.1007/S00373-019-02084-5MaRDI QIDQ2287748zbMATH OpenOpenAlexWikidataFDO

Authors Hemanshu Kaul, J. A. Mudrock

Publication date 21 January 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

Cartesian productchromatic choosable graphgraph coloringlist coloringlist-color function

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Abstract: We study the list chromatic number of the Cartesian product of any graph $G$ and a complete bipartite graph with partite sets of size $a$ and $b$, denoted $ch{i}_{e}ll(Gsquare{K}_{a,b})$. We have two motivations. A classic result on the gap between list chromatic number and the chromatic number tells us $ch{i}_{e}ll(K_{a,b})=1+a$ if and only if $bgeq{a}^a$. Since $ch{i}_{e}ll(K_{a,b})leq1+a$ for any $binmathbbN$, this result tells us the values of $b$ for which $ch{i}_{e}ll(K_{a,b})$ is as large as possible and far from $chi(K_{a,b})=2$. In this paper we seek to understand when $ch{i}_{e}ll(Gsquare{K}_{a,b})$ is far from $chi(Gsquare{K}_{a,b})=maxchi(G),2$. It is easy to show $ch{i}_{e}ll(Gsquare{K}_{a,b})leqch{i}_{e}ll(G)+a$. In 2006, Borowiecki, Jendrol, Kr'al, and Miskuf showed that this bound is attainable if $b$ is sufficiently large; specifically, $ch{i}_{e}ll(Gsquare{K}_{a,b})=ch{i}_{e}ll(G)+a$ whenever $bgeq(ch{i}_{e}ll(G)+a-1{)}^{a|V(G)|}$. Given any graph $G$ and $ainmathbbN$, we wish to determine the smallest $b$ such that $ch{i}_{e}ll(Gsquare{K}_{a,b})=ch{i}_{e}ll(G)+a$. In this paper we show that the list color function, a list analogue of the chromatic polynomial, provides the right concept and tool for making progress on this problem. Using the list color function, we prove a general improvement on Borowiecki et al.'s 2006 result, and we compute the smallest such $b$ exactly for some large families of chromatic-choosable graphs.

Recommendations

• List coloring of Cartesian products of graphs
• Criticality, the list color function, and list coloring the Cartesian product of graphs
• Bipartite graphs whose squares are not chromatic-choosable
• scientific article; zbMATH DE number 166081
• DP‐coloring Cartesian products of graphs

Cites work

• A proof of a conjecture of Ohba
• An introduction to chromatic polynomials
• Choice number of 3-colorable elementary graphs
• Choosability of powers of circuits
• Criticality, the list color function, and list coloring the Cartesian product of graphs
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 889958 (Why is no real title available?)
• List coloring and n-monophilic graphs.
• List coloring of Cartesian products of graphs
• List edge and list total colourings of multigraphs
• On chromatic‐choosable graphs
• Some upper bounds on the total and list chromatic numbers of multigraphs
• The chromatic polynomial and list colorings
• The list chromatic index of a bipartite multigraph
• When does the list-coloring function of a graph equal its chromatic polynomial

Cited in

(9)

• Criticality, the list color function, and list coloring the Cartesian product of graphs
• List coloring of Cartesian products of graphs
• Fractional DP-chromatic number of planar graphs of large girth
• DP‐coloring Cartesian products of graphs
• Bounding the list color function threshold from above
• Flexible list colorings: maximizing the number of requests satisfied
• List coloring the Cartesian product of a complete graph and complete bipartite graph
• On the Ohba number and generalized Ohba numbers of complete bipartite graphs
• On the DP-chromatic number of Cartesian products of critical graphs

This page was built for publication: List coloring a Cartesian product with a complete bipartite factor

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