Published March 1, 2024
| Version v1
Publication
Open
On the total chromatic number of the direct product of cycles and complete graphs
Creators
- 1. Universidade Federal de Goiás
- 2. Universidade Federal do Rio de Janeiro
- 3. Universidade Federal Fluminense
- 4. Instituto Federal de Goiás
- 5. Universidade do Estado do Rio de Janeiro
- 6. Université de Lorraine
- 7. Lorraine Research Laboratory in Computer Science and its Applications
Description
A k-total coloring of a graph G is an assignment of k colors to the elements (vertices and edges) of G so that adjacent or incident elements have different colors. The total chromatic number is the smallest integer k for which G has a k -total coloring. The well known Total Coloring Conjecture states that the total chromatic number of a graph is either Δ( G ) + 1 (called Type 1) or Δ( G ) + 2 (called Type 2), where Δ( G ) is the maximum degree of G . We consider the direct product of complete graphs K m × K n . It is known that if at least one of the numbers m or n is even, then K m × K n is Type 1, except for K 2 × K 2 . We prove that the graph K m × K n is Type 1 when both m and n are odd numbers, by using that the conformable condition is sufficient for the graph K m × K n to be Type 1 when both m and n are large enough, and by constructing the target total colorings by using Hamiltonian decompositions and a specific color class, called guiding color. We additionally apply our technique to the direct product C m × K n of a cycle with a complete graph. Interestingly, we are able to find a Type 2 infinite family C m × K n , when m is not a multiple of 3 and n = 2. We provide evidence to conjecture that all other C m × K n are Type 1.
Translated Descriptions
⚠️
This is an automatic machine translation with an accuracy of 90-95%
Translated Description (Arabic)
التلوين الكلي للرسم البياني G هو تعيين ألوان k للعناصر (الرؤوس والحواف) من G بحيث يكون للعناصر المجاورة أو الساقطة ألوان مختلفة. العدد اللوني الإجمالي هو أصغر عدد صحيح يحتوي G على k - total coloring. تنص تخمينات التلوين الإجمالية المعروفة جيدًا على أن العدد اللوني الإجمالي للرسم البياني هو إما Δ( G ) + 1 (يسمى النوع 1) أو Δ( G ) + 2 (يسمى النوع 2)، حيث Δ( G ) هي الدرجة القصوى لـ G . نعتبر الناتج المباشر للرسوم البيانية الكاملة Km × Kn. من المعروف أنه إذا كان واحد على الأقل من الأرقام م أو ن زوجياً، فإن ك م × ك ن هو النوع 1، باستثناء ك 2 × ك 2 . نثبت أن الرسم البياني K m × K n هو النوع 1 عندما يكون كل من m و n أعدادًا فردية، وذلك باستخدام أن الحالة المتوافقة كافية للرسم البياني K m × K n ليكون النوع 1 عندما يكون كل من m و n كبيرًا بما فيه الكفاية، وعن طريق بناء إجمالي الألوان المستهدفة باستخدام تحلل هاملتوني وفئة لون محددة، تسمى اللون التوجيهي. بالإضافة إلى ذلك، نطبق تقنيتنا على المنتج المباشر Cm × Kn للدورة مع رسم بياني كامل. ومن المثير للاهتمام أننا قادرون على العثور على عائلة لانهائية من النوع 2 Cm × Kn، عندما لا يكون m من مضاعفات 3 و n = 2. نحن نقدم أدلة على التخمين بأن جميع المواد الأخرى هي من النوع 1.Translated Description (French)
Une coloration k-total d'un graphique G est une affectation de k couleurs aux éléments (sommets et arêtes) de G afin que les éléments adjacents ou incidents aient des couleurs différentes. Le nombre chromatique total est le plus petit entier k pour lequel G a une coloration k-total. La conjecture de coloration totale bien connue indique que le nombre chromatique total d'un graphe est soit Δ( G ) + 1 (appelé Type 1) ou Δ( G ) + 2 (appelé Type 2), où Δ( G ) est le degré maximum de G . Nous considérons le produit direct de graphiques complets K m × K n . On sait que si au moins l'un des nombres m ou n est pair, alors K m × K n est de type 1, à l'exception de K 2 × K 2 . Nous prouvons que le graphique K m × K n est de type 1 lorsque m et n sont des nombres impairs, en utilisant que la condition conforme est suffisante pour que le graphique K m × K n soit de type 1 lorsque m et n sont suffisamment grands, et en construisant les colorations totales cibles en utilisant des décompositions hamiltoniennes et une classe de couleur spécifique, appelée couleur directrice. Nous appliquons en outre notre technique au produit direct C m × K n d'un cycle avec un graphe complet. Fait intéressant, nous sommes en mesure de trouver une famille infinie de type 2 C m × K n , lorsque m n'est pas un multiple de 3 et n = 2. Nous fournissons des preuves pour conjecturer que tous les autres C m × K n sont de type 1.Translated Description (Spanish)
Una coloración k-total de un gráfico G es una asignación de k colores a los elementos (vértices y aristas) de G para que los elementos adyacentes o incidentes tengan diferentes colores. El número cromático total es el entero más pequeño k para el que G tiene una coloración k -total. La conocida Conjetura de coloración total establece que el número cromático total de un gráfico es Δ( G ) + 1 (llamado Tipo 1) o Δ( G ) + 2 (llamado Tipo 2), donde Δ( G ) es el grado máximo de G. Consideramos el producto directo de los gráficos completos K m × K n . Se sabe que si al menos uno de los números m o n es par, entonces K m × K n es Tipo 1, a excepción de K 2 × K 2 . Demostramos que el gráfico K m × K n es de Tipo 1 cuando tanto m como n son números impares, utilizando que la condición conformable es suficiente para que el gráfico K m × K n sea de Tipo 1 cuando tanto m como n son lo suficientemente grandes, y construyendo las coloraciones totales objetivo mediante el uso de descomposiciones hamiltonianas y una clase de color específica, llamada color guía. Además, aplicamos nuestra técnica al producto directo C m × K n de un ciclo con un gráfico completo. Curiosamente, podemos encontrar una familia infinita de tipo 2 C m × K n , cuando m no es un múltiplo de 3 y n = 2. Proporcionamos evidencia para conjeturar que todos los demás C m × K n son Tipo 1.Files
ro230047.pdf.pdf
Files
(24 Bytes)
| Name | Size | Download all |
|---|---|---|
|
md5:7624dcbc096921e31a1da610e19a546e
|
24 Bytes | Preview Download |
Additional details
Additional titles
- Translated title (Arabic)
- على العدد اللوني الكلي للمنتج المباشر للدورات والرسوم البيانية الكاملة
- Translated title (French)
- Sur le nombre chromatique total du produit direct des cycles et des graphiques complets
- Translated title (Spanish)
- Sobre el número cromático total del producto directo de ciclos y gráficos completos
Identifiers
- Other
- https://openalex.org/W4391906507
- DOI
- 10.1051/ro/2024045
References
- https://openalex.org/W1978873763
- https://openalex.org/W1996845414
- https://openalex.org/W2044410117
- https://openalex.org/W2050181703
- https://openalex.org/W2082080785
- https://openalex.org/W2146117644
- https://openalex.org/W2160642345
- https://openalex.org/W2792907414
- https://openalex.org/W4205332200
- https://openalex.org/W4321381759