Zero-divisor graphs and total coloring conjecture
- PDF / 583,447 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 77 Downloads / 193 Views
FOUNDATIONS
Zero-divisor graphs and total coloring conjecture Nilesh Khandekar1 · Vinayak Joshi1
© Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract In this paper, we prove that the zero-divisor graphs of a special class of pseudocomplemented posets satisfy the total coloring conjecture. Also, we determine the edge chromatic number of the zero-divisor graphs of this special class of pseudocomplemented posets. These results are applied to zero-divisor graphs of finite reduced commutative rings. Keywords Zero-divisor graphs · Coloring of a graph · Total coloring conjecture · Pseudocomplemented poset · Direct product of posets · Reduced ring
1 Introduction The coloring of graphs is a central problem in Graph Theory. It mainly deals with the partitioning a set of objects into classes following certain rules. Galvin and Komjath (1991) proved that the fact that any finite or infinite graph has a chromatic number is equivalent to the Axiom of Choice. There are many famous colorings of graphs, such as vertex coloring, edge coloring, total coloring, etc. The vertex chromatic number χ (G) of a graph G is the minimum number of colors required to color the vertices of G such that no two adjacent vertices receive the same color. The edge coloring refers back to Tait’s attempts around 1880 to prove the Four-color problem. Edge coloring received less attention compared to the vertex coloring. The edge chromatic number χ (G) of a graph G is the minimum number of colors required to color the edges of G such that adjacent edges receive different colors. Vizing (1964, 1965) obtained an upper bound for the edge chromatic number of a graph G. It should be noted that Gupta (1967) also independently calculated the same bound for χ (G) in terms of the maximum degree (G).
Communicated by A. Di Nola.
B
Vinayak Joshi [email protected]; [email protected] Nilesh Khandekar [email protected]
1
Department of Mathematics, Savitribai Phule Pune University, Pune 411007, Maharashtra, India
Theorem 1.1 [Vizing–Gupta theorem (Stiebitz et al. 2012)] If G is a finite simple graph, then either χ (G) = (G) or χ (G) = (G) + 1. A graph G is class one, if χ (G) = (G) and is class two, if χ (G) =(G)+1. Another famous coloring of graphs is the total coloring. Total coloring of a graph G is an assignment of colors to the vertices and the edges of G such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number χ (G) of a graph G is the minimum number of colors needed in a total coloring of G. Total coloring was introduced by Vizing (1964, 1965) and independently by Behzad (1965) in his Ph.D. Thesis. They both formulated the following conjecture, now known as, the Total Coloring Conjecture. Total Coloring Conjecture: Let G be a finite simple undirected graph. Then χ (G) = (G) + 1 or χ (G) = (G) + 2. Note that every graph G requires at least (G) + 1 colors for the total coloring. A gra
Data Loading...
