HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:41:00 PM
Last modification on : Friday, February 4, 2022 - 3:20:08 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