التفاصيل البيبلوغرافية
| العنوان: |
On the coequal values of total chromatic number and chromatic index. |
| المؤلفون: |
Chen, Guantao1 (AUTHOR) gchen@gsu.edu, Hao, Yanli1 (AUTHOR) yhao4@gsu.edu |
| المصدر: |
Journal of Combinatorial Theory - Series B. Jan2023:Part 2, Vol. 158, p286-304. 19p. |
| مصطلحات موضوعية: |
*INDEX numbers (Economics), *GRAPH coloring, *MULTIGRAPH, *GRAPH theory |
| مستخلص: |
The chromatic index χ ′ (G) of a graph G is the least number of colors assigned to the edges of G such that no two adjacent edges receive the same color. The total chromatic number χ ″ (G) of a graph G is the least number of colors assigned to the edges and vertices of G such that no two adjacent edges receive the same color, no two adjacent vertices receive the same color and no edge has the same color as its two endpoints. The chromatic index and the total chromatic number are two of few fundamental graph parameters, and their correlation has always been a subject of intensive study in graph theory. By definition, χ ′ (G) ≤ χ ″ (G) for every graph G. In 1984, Goldberg conjectured that for any multigraph G , if χ ′ (G) ≥ Δ (G) + 3 then χ ″ (G) = χ ′ (G). In this paper, we show that Goldberg's conjecture is asymptotically true. More specifically, we prove that for a multigraph G with maximum degree Δ sufficiently large, χ ″ (G) = χ ′ (G) provided χ ′ (G) ≥ Δ + 10 Δ 35 / 36. When χ ′ (G) ≥ Δ (G) + 2 , the chromatic index χ ′ (G) is completely determined by the fractional chromatic index. Consequently, the total chromatic number χ ″ (G) can be computed in polynomial-time in this case. [ABSTRACT FROM AUTHOR] |
| قاعدة البيانات: |
Academic Search Index |
