2025-11-10T03:06:56.403525

List Packing and Correspondence Packing of Planar Graphs

Cranston, Smith-Roberge
For a graph $G$ and a list assignment $L$ with $|L(v)|=k$ for all $v$, an $L$-packing consists of $L$-colorings $φ_1,\cdots,φ_k$ such that $φ_i(v)\neφ_j(v)$ for all $v$ and all distinct $i,j\in\{1,\ldots,k\}$. Let $χ^{\star}_{\ell}(G)$ denote the smallest $k$ such that $G$ has an $L$-packing for every $L$ with $|L(v)|=k$ for all $v$. Let $\mathcal{P}_k$ denote the set of all planar graphs with girth at least $k$. We show that (i) $χ^{\star}_{\ell}(G)\le 8$ for all $G\in \mathcal{P}_3$ and (ii) $χ^{\star}_{\ell}(G)\le 5$ for all $G\in \mathcal{P}_4$ and (iii) $χ^{\star}_{\ell}(G)\le 4$ for all $G\in \mathcal{P}_5$. Part (i) makes progress on a problem of Cambie, Cames van Batenburg, Davies, and Kang. We also construct outerplanar graphs $G$ such that $χ^{\star}_{\ell}(G)=4$, which matches the known upper bound $χ^{\star}_{\ell}(G)\le 4$ for all outerplanar graphs. Finally, we consider the analogue of $χ^{\star}_{\ell}$ for correspondence coloring, $χ^{\star}_c$. In fact, all bounds stated above for $χ^{\star}_{\ell}$ also hold for $χ^{\star}_c$.
academic

Empaquetage de Listes et Empaquetage de Correspondance des Graphes Planaires

Informations Fondamentales

  • ID de l'article: 2401.01332
  • Titre: List Packing and Correspondence Packing of Planar Graphs
  • Auteurs: Daniel W. Cranston (Virginia Commonwealth University), Evelyne Smith-Roberge (Georgia Tech)
  • Classification: math.CO (Mathématiques Combinatoires)
  • Date de publication: 6 décembre 2024 (version 3 sur arXiv)
  • Lien de l'article: https://arxiv.org/abs/2401.01332

Résumé

Cet article étudie les problèmes d'empaquetage de listes (list packing) et d'empaquetage de correspondance (correspondence packing) pour les graphes planaires. Pour un graphe GG et une assignation de listes LL, où ∣L(v)∣=k|L(v)|=k pour tous les sommets vv, un LL-empaquetage contient des LL-colorations ϕ1,⋯ ,ϕk\phi_1,\cdots,\phi_k telles que pour tous vv et tous i,j∈{1,…,k}i,j\in\{1,\ldots,k\} distincts, on ait ϕi(v)≠ϕj(v)\phi_i(v)\neq\phi_j(v). Soit χℓ⋆(G)\chi^{\star}_{\ell}(G) la plus petite valeur de kk telle que GG admette un LL-empaquetage pour chaque assignation LL avec ∣L(v)∣=k|L(v)|=k. L'article démontre que: (i) pour tous les graphes planaires GG de maille au moins 3, χℓ⋆(G)≤8\chi^{\star}_{\ell}(G)\leq 8; (ii) pour tous les graphes planaires GG de maille au moins 4, χℓ⋆(G)≤5\chi^{\star}_{\ell}(G)\leq 5; (iii) pour tous les graphes planaires GG de maille au moins 5, χℓ⋆(G)≤4\chi^{\star}_{\ell}(G)\leq 4. Ces résultats s'étendent également au paramètre analogue χc⋆\chi^{\star}_c pour les colorations de correspondance.

Contexte et Motivation de la Recherche

  1. Problème fondamental: Étudier les bornes supérieures du nombre d'empaquetage de listes et du nombre d'empaquetage de correspondance pour les graphes planaires. L'empaquetage de listes est une généralisation de la coloration de listes, exigeant de trouver plusieurs colorations de listes disjointes.
  2. Importance du problème:
    • La coloration de listes est un problème classique en théorie des graphes, avec une valeur théorique et applicative considérable
    • Les problèmes d'empaquetage sont des généralisations naturelles des problèmes de coloration, étudiant l'optimisation de l'allocation de ressources
    • Les graphes planaires, en tant que classe importante, possèdent des propriétés de coloration d'une signification théorique particulière
  3. Limitations existantes:
    • Cambie et al. ont démontré en 2024 que χc⋆(G)≤10\chi^{\star}_c(G)\leq 10 pour tous les graphes planaires GG
    • Cette borne est relativement grossière et nécessite une amélioration supplémentaire
    • L'analyse fine des graphes planaires de mailles différentes fait défaut
  4. Motivation de la recherche:
    • Améliorer les bornes connues, en particulier celles proposées par Cambie et al.
    • Établir la relation précise entre la maille et le nombre d'empaquetage
    • Fournir un cadre d'analyse unifié pour la coloration de correspondance

Contributions Principales

  1. Amélioration significative des bornes d'empaquetage pour les graphes planaires: Amélioration de χc⋆(G)≤10\chi^{\star}_c(G)\leq 10 à χc⋆(G)≤8\chi^{\star}_c(G)\leq 8
  2. Établissement de la relation précise entre la maille et le nombre d'empaquetage:
    • Maille ≥ 4: χc⋆(G)≤5\chi^{\star}_c(G)\leq 5
    • Maille ≥ 5: χc⋆(G)≤4\chi^{\star}_c(G)\leq 4 (optimal)
  3. Fourniture de preuves entièrement vérifiables manuellement: Contrairement aux travaux contemporains, évite la vérification informatique
  4. Traitement unifié de l'empaquetage de listes et de l'empaquetage de correspondance: Tous les résultats s'appliquent aux deux types d'empaquetage
  5. Démonstration de l'optimalité dans le cas de maille ≥ 5: Par construction d'exemples montrant que les bornes sont serrées

Explication Détaillée des Méthodes

Définitions des Tâches

Empaquetage de listes: Étant donné un graphe GG et une kk-assignation LL (chaque sommet vv dispose de ∣L(v)∣=k|L(v)|=k couleurs disponibles), trouver kk colorations LL distinctes ϕ1,…,ϕk\phi_1,\ldots,\phi_k telles que:

  1. Chaque ϕi\phi_i est une coloration LL valide
  2. Pour tout sommet vv et tous i,ji,j distincts, on a ϕi(v)≠ϕj(v)\phi_i(v)\neq\phi_j(v)

Empaquetage de correspondance: Définition analogue, mais utilisant la coloration de correspondance au lieu de la coloration de listes, avec des contraintes plus fortes.

Cadre Technique Principal

1. Méthode du Graphe Biparti Auxiliaire

  • Définition: Pour un sommet vv et un empaquetage existant ϕ\phi, construire un graphe biparti auxiliaire HvH_v
  • Partie A: Représente les kk couleurs
  • Partie B: Représente les kk colorations ϕ1,…,ϕk\phi_1,\ldots,\phi_k
  • Arêtes: iϕj∈E(H)i\phi_j \in E(H) si et seulement si on peut définir ϕj(v)=i\phi_j(v)=i

2. Application du Théorème de Hall

Utiliser le théorème de Hall pour déterminer si un graphe biparti possède un appariement parfait:

  • Obstacle: Ensemble X⊆AX \subseteq A satisfaisant ∣N(X)∣<∣X∣|N(X)| < |X|
  • Observation clé: La taille des obstacles dans un graphe biparti (s,t)(s,t) est limitée

3. Outils d'Analyse Structurelle

Proposition 5: Si GG est un graphe biparti (s,t)(s,t) et qu'il existe X⊆AX \subseteq A tel que ∣X∣>∣N(X)∣|X| > |N(X)|, alors t+1≤∣X∣≤s−tt+1 \leq |X| \leq s-t.

Corollaire 6: Si χc⋆(G−v)≤k\chi^{\star}_c(G-v) \leq k et d(v)≤k/2d(v) \leq k/2, alors χc⋆(G)≤k\chi^{\star}_c(G) \leq k.

Stratégies Principales de Preuve

1. Cas de Maille ≥ 4 (Théorème 12)

  • Méthode de décharge: Assigner une charge initiale à chaque sommet égale à son degré
  • Règles de décharge: Chaque sommet de degré 3 reçoit une charge de 1/31/3 de chaque voisin
  • Configurations interdites:
    • Les sommets de degré 3 ne peuvent pas être adjacents
    • Il n'existe pas d'arête vwvw telle que d(v)=3d(v)=3 et d(w)≤4d(w) \leq 4
    • Les sommets de degré 5 sont adjacents à au plus 3 sommets de degré 3

2. Cas de Maille ≥ 5 (Théorème 15)

Utiliser une analyse plus fine:

  • Lemme clé: Chaque sommet d'un graphe biparti (4,2)(4,2) est incident à au moins deux arêtes contenues dans un 1-facteur
  • Analyse de chemins: Traitement particulier des chemins xvyxvy formés par des sommets de degré 3
  • Technique de ré-empaquetage: Modifier les colorations des sommets voisins pour créer de l'espace d'extension pour le sommet cible

3. Cas des Graphes Planaires Généraux (Théorème 19)

  • Théorème de structure de Borodin: Un graphe planaire avec δ(G)≥5\delta(G) \geq 5 contient un triangle uvwuvw tel que d(u)+d(v)+d(w)≤17d(u)+d(v)+d(w) \leq 17
  • Analyse des types d'obstacles: Définir 4 types d'obstacles et les traiter séparément
  • Ré-empaquetage complexe: Peut nécessiter la modification simultanée des colorations de deux sommets

Configuration Expérimentale

Cet article est un travail purement théorique ne nécessitant pas de vérification expérimentale. Tous les résultats sont obtenus par des preuves mathématiques rigoureuses.

Innovations Techniques Principales

1. Système de Classification des Obstacles

Définition de 4 types d'obstacles dans les graphes bipartis (8,3)(8,3):

  • Type 1: ∣X∣=5|X|=5, ∣N(X)∣=3|N(X)|=3
  • Type 2: ∣X∣=4|X|=4, ∣N(X)∣=3|N(X)|=3, avec une structure d'extension spécifique
  • Type 3: Similaire au type 2 mais avec une structure d'extension différente
  • Type 4: Cas ∣X∣=4|X|=4, ∣N(X)∣=3|N(X)|=3 n'appartenant pas aux trois premiers types

2. Cadre d'Analyse Unifié

Par le lemme 8, établir l'équivalence entre la coloration de listes et la coloration de correspondance, permettant de "redresser" les arrangements sur les structures arborescentes.

3. Contraintes de Degré Précises

Utiliser la formule d'Euler pour établir la relation entre la maille et le degré moyen:

  • Graphe planaire de maille gg avec degré moyen maximal <2g/(g−2)< 2g/(g-2)
  • Maille 4: degré moyen <4< 4
  • Maille 5: degré moyen <10/3< 10/3

Résultats Principaux

Énoncés des Théorèmes

  1. Théorème 1: χc⋆(G)≤8\chi^{\star}_c(G) \leq 8 pour tous les graphes planaires GG
  2. Théorème 2: χc⋆(G)≤5\chi^{\star}_c(G) \leq 5 pour tous les graphes planaires GG de maille ≥ 4
  3. Théorème 3: χc⋆(G)≤4\chi^{\star}_c(G) \leq 4 pour tous les graphes planaires GG de maille ≥ 5, et cette borne est optimale

Optimalité

Démonstration par l'exemple des cycles CkC_k (k≥3k \geq 3):

  • χℓ⋆(Ck)=3<4=χc⋆(Ck)\chi^{\star}_\ell(C_k) = 3 < 4 = \chi^{\star}_c(C_k)
  • Montrant que l'empaquetage de correspondance est plus difficile que l'empaquetage de listes
  • La borne 4 pour la maille ≥ 5 est serrée

Travaux Connexes

  1. Cambie et al. (2024): Première étude systématique des problèmes d'empaquetage, démontrant χc⋆(G)≤10\chi^{\star}_c(G) \leq 10
  2. Travaux contemporains: Travail indépendant de Cambie, Cames van Batenburg, Zhu démontrant les mêmes résultats mais dépendant de la vérification informatique
  3. Théorie classique de la coloration: Fondée sur les travaux classiques de Heawood, Ringel-Youngs et autres sur la coloration des graphes sur surfaces
  4. Coloration de correspondance: Cadre théorique établi par Dvořák-Postle et al.

Conclusions et Discussion

Conclusions Principales

  1. Amélioration significative des bornes du nombre d'empaquetage pour les graphes planaires
  2. Établissement de la relation précise entre la maille et le nombre d'empaquetage
  3. Fourniture d'une méthode de preuve entièrement constructive
  4. Traitement unifié de l'empaquetage de listes et de l'empaquetage de correspondance

Limitations

  1. Les preuves sont très techniques, impliquant une analyse de nombreux cas
  2. Les problèmes pour les graphes sur surfaces générales restent non résolus
  3. L'optimalité de certaines bornes n'est pas entièrement déterminée

Directions Futures

L'article propose 6 problèmes ouverts:

  1. Déterminer les valeurs précises de χℓ⋆(P3)\chi^{\star}_\ell(\mathcal{P}_3) et χℓ⋆(P4)\chi^{\star}_\ell(\mathcal{P}_4)
  2. Étudier le nombre d'empaquetage pour les classes de graphes avec degré moyen maximal borné
  3. Problèmes d'empaquetage pour les graphes planaires bipartis
  4. Nombre d'empaquetage pour les graphes sur surfaces générales
  5. Relation avec le nombre de Heawood
  6. Nombre d'empaquetage pour les graphes sans sous-graphes complets

Évaluation Approfondie

Avantages

  1. Contribution théorique majeure: Amélioration significative des bornes pour un problème important
  2. Innovation méthodologique: La classification des obstacles et le cadre d'analyse unifié ont une portée générale
  3. Preuves complètes: Évite la vérification informatique, toutes les preuves peuvent être vérifiées manuellement
  4. Résultats optimaux: Le cas de maille ≥ 5 atteint la borne optimale
  5. Rédaction claire: Les détails techniques sont bien organisés, les exemples facilitent la compréhension

Insuffisances

  1. Preuves complexes: Nombreux détails techniques et analyses de cas
  2. Généralisation: L'applicabilité des méthodes à d'autres classes de graphes n'est pas claire
  3. Complexité computationnelle: Les aspects algorithmiques ne sont pas discutés

Impact

  1. Valeur théorique: Avance le développement de la théorie de la coloration des graphes
  2. Valeur méthodologique: Les outils techniques peuvent s'appliquer à d'autres problèmes
  3. Problèmes ouverts: Les questions proposées fournissent des directions pour les recherches futures

Domaines d'Application

  1. Évitement de conflits dans l'allocation de ressources
  2. Allocation de spectre et coloration de réseaux
  3. Problèmes d'ordonnancement avec contraintes de satisfaction
  4. Problèmes d'empaquetage en optimisation combinatoire

Références

L'article cite 20 références importantes, notamment:

  • Résultats classiques de Borodin sur la structure des graphes planaires
  • Travail fondateur de Cambie et al. sur les problèmes d'empaquetage
  • Théorie de la coloration de correspondance de Dvořák-Postle
  • Théorie classique de Heawood sur la coloration des graphes sur surfaces

Cet article apporte une contribution importante en mathématiques combinatoires, en particulier en théorie de la coloration des graphes. Par des techniques ingénieuses, il améliore significativement les bornes du problème d'empaquetage pour les graphes planaires, posant ainsi des fondations solides pour le développement ultérieur de ce domaine.