Skip to Main content Skip to Navigation

Choosability of bipartite graphs with maximum degree $Delta$

Stéphane Bessy 1 Frédéric Havet Jérôme Palaysi
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Let G=(V(G), E(G)) be a graph. A list assignment is an assignment of a set L(v) of integers to every vertex v of G. An L-colouring is an application C from V(G) into the set of integers such that C(v)L(v) for all v V(G) and C(u)C(v) if u and v are joined by an edge. A (k,k')-list assignment of a bipartite graph G with bipartition (A,B) is a list assignment L such that |L(v)|= k if vA and |L(v)|= k' if vB. A bipartite graph is (k,k')-choosable if it admits an L-colouring for every (k.k')-list assignment L. In this paper, we study the (k,k')-choosability of graphs. Alon and Tarsi proved in an algebraic and non-constructive way, that every bipartite graph with maximum degree is (/2 +1, /2 +1)-choosable. In this paper, we give an alternative and constructive proof to this result. We conjecture that this result is sharp (i.e. there is a bipartite graph with maximum degree that is not (/2 , /2 +1)-choosable) and prove it for 5. Moreover, for a fixed , we show that given a bipartite graph with maximum degree and a (/2 , /2)+1)-list assignment L, it is NP-complete to decide if G is L-colourable. At last, we give upper bounds for the minimum size n_3() of a non (3,3)-choosable bipartite graph with maximum degree : n_3(5)846 and n_3(6)128.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:41:00 PM
Last modification on : Monday, October 12, 2020 - 10:30:20 AM
Long-term archiving on: : Sunday, April 4, 2010 - 8:57:50 PM


  • HAL Id : inria-00072066, version 1



Stéphane Bessy, Frédéric Havet, Jérôme Palaysi. Choosability of bipartite graphs with maximum degree $Delta$. RR-4522, INRIA. 2002. ⟨inria-00072066⟩



Record views


Files downloads