Combien de couleurs distinctes faut-il pour réduire la possibilité de choisir un graphique?

39

Un graphe est -choosable (également appelé -list-colorable ) si, pour toute fonction qui mappe des sommets sur des ensembles de couleurs, il existe une affectation de couleur telle que, pour tous les sommets , , et tel que, pour tous les , .k f k c v c ( v ) f ( v ) v w c ( v ) c ( w )kkfkcvc(v)f(v)vwc(v)c(w)

Supposons maintenant qu'un graphe ne soit pas choquable. C'est-à-dire qu'il existe une fonction des sommets à -tuples de couleurs qui n'a pas d'affectation de couleur valide . Ce que je veux savoir, c'est combien de couleurs au total sont nécessaires? Quelle peut être la taille de ? Existe-t-il un nombre (indépendant de ) tel que nous pouvons être assurés de trouver un incolorable qui utilise uniquement couleurs distinctes?k f k c v G f ( v ) N ( k ) G f N ( k )GkfkcvGf(v)N(k)GfN(k)

La pertinence pour CS est que, si existe, nous pouvons tester -choosabilité de constant en temps simple-exponentiel (essayez simplement tous les \ binom {N (k)} {k} ^ n choix de f , et pour chacun, vérifiez qu’il peut être coloré dans le temps k ^ nn ^ {O (1)} ), sinon il pourrait être nécessaire d’ obtenir une croissance plus rapide comme n ^ {kn} .k k ( N ( k )N(k)kk(N(k)k)nk n n O ( 1 ) n k nfknnO(1)nkn

David Eppstein
la source
1
Existe-t-il un exemple lorsque N (k)> 2k-1?
Yaroslav Bulatov
1
Ma première idée est d'essayer de réduire le nombre de couleurs requises dans l'exemple standard selon lequel les graphes bipartites peuvent avoir un nombre liste-chromatique arbitrairement élevé. Cependant, le nombre de couleurs de la liste dans cette construction est exponentiel au k obtenu k. Je n'ai cependant pas pris assez de temps pour prouver la limite inférieure (donc ce n'est pas une réponse ... pour l'instant).
Derrick Stolee
1
Cela vaut peut-être la peine de poser aussi cette excellente question sur MathOverflow ...
François G. Dorais
Ne réglage k=1 dans Corollaire 1.4 ici répondre à au moins une partie de votre question?
Aaron Sterling
@Aaron: Je ne suis pas sûr de ce que vous voulez dire. Si je fixe k = 1 dans ce corollaire, il semblerait que le nombre choisi soit au plus le nombre chromatique multiplié par le facteur de log; mais cela ne semble pas dire grand chose sur le nombre de couleurs distinctes nécessaires pour ce nombre de choix.
David Eppstein

Réponses:

21

Daniel Král et Jiří Sgall ont répondu négativement à votre question. Extrait du résumé de leur article:

Un graphe est dit -choosable si ses sommets peuvent être colorés à partir de n'importe quelle liste avec , pour tout et avec . Pour chaque , nous construisons un graphe qui est -choosable mais pas -choosable.( k , ) L ( v ) | L ( v ) | k v V ( G ) | v V ( G ) L ( v ) | 3 k G ( k , ) ( k , + 1 )g(k,)L(v)|L(v)|kvV(g)|vV(g)L(v)|3kg(k,)(k,+1)

Donc, n’existe pas si . Král et Sgall montrent également que . Bien entendu, .k 3 N ( 2 ) = 4 N ( 1 ) = 1N(k)k3N(2)=4N(1)=1

Daniel Král, Jiří Sgall: Coloration de graphiques à partir de listes avec la taille limitée de leur union . Journal of Graph Theory 49 (3): 177-186 (2005)

Serge Gaspers
la source
Sensationnel. Cela règle la question, bien que négativement. Merci @Serge! Et j'aimerais pouvoir remercier Daniel et Jiří aussi!
Hsien-Chih Chang le
J'aurais aussi préféré une réponse positive à la question.
Serge Gaspers
8

En guise d’auto-promotion sans honte, Marthe Bonamy et moi avons trouvé plus de réponses négatives. En particulier, le théorème 4 de http://arxiv.org/abs/1507.03495 améliore le résultat susmentionné de Král 'et de Sgall dans certains cas. Les exemples que nous utilisons sont des graphes bipartites complets, dans lesquels nous avons utilisé une combinatoire extrême pour les analyser.

Le travail a été motivé en partie par cette question de débordement du SDC.

RJK
la source