Choosability of bipartite graphs with maximum degree $Delta$ - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport Année : 2002

Choosability of bipartite graphs with maximum degree $Delta$

Frédéric Havet
Jérôme Palaysi
  • Fonction : Auteur
  • PersonId : 938554

Résumé

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.

Domaines

Autre [cs.OH]
Fichier principal
Vignette du fichier
RR-4522.pdf (253.25 Ko) Télécharger le fichier
Loading...

Dates et versions

inria-00072066 , version 1 (23-05-2006)

Identifiants

  • HAL Id : inria-00072066 , version 1

Citer

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⟩
129 Consultations
487 Téléchargements

Partager

Gmail Facebook X LinkedIn More