Equitable coloring of graph products

• Autorzy: Furmańczyk H.
• Języki publikacji: EN

Abstrakty

EN

A graph is equitably k-colorable if its vertices can be partitioned into k independent sets in such a way that the number of vertices in any two sets differ by at most one. The smallest k for which such a coloring exists is known as the "equitable chromatic number" of G and denoted by χ=(G). It is interesting to note that if a graph G is equitably k-colorable, it does not imply that it is equitably (k + 1)-colorable. The smallest integer k for which G is equitably k'-colorable for all k' ≥ k is called "the equitable chromatic threshold" of G and denoted by χ*=(G). In the paper we establish the equitable chromatic number and the equitable chromatic threshold for certain products of some highly-structured graphs. We extend the results from [2] for Cartesian, weak and strong tensor products.

Słowa kluczowe

EN

equitable coloring; graph product

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2006
• Tom: Vol. 26, no. 1
• Strony: 31--44
• Opis fizyczny: Bibliogr 15 poz., rys.

Twórcy

autor

Furmańczyk H.

• Gdańsk University, Mathematical Institute, Wita Stwosza Street 57, 80-952 Gdańsk, Poland,

Bibliografia

• [1] Chen B.-L., Lih K.-W., Equitable coloring of trees, J. Combin. Theory, Ser. B 61 (1994), 83-87
• [2] Chen B.-L., Lih K.-W., Yan J.-H., Equitable coloring of graph products, manuscript, 1998.
• [3] Feigenbaum J., Schaffer N. W., Finding the prime factors of strong direct product graphs in polynomial time, Discrete Math., 109 (1992), 77-102.
• [4] Furmańczyk H., Equitable coloring of graphs, in: M. Kubale (ed.), Optymalizacja dyskretna. Modele i metody kolorowania grafów, WNT Warszawa 2002, 72-92 (in Polish).
• [5] Hajnal A., Szemeredi E., Proof of a conjecture of Erdos, in: Combinatorial Theory and Its Applications, II 601-623, Colloq. Math. Soc. Jnos Bolyai, Vol. 4, North-Holland, Amsterdam, 1970.
• [6] Hedetniemi S., Homomorphism of graphs and automata, Univ. Michigan, Technical Report 03105-44-T, 1966.
• [7] Imrich W., Factoring cardinal product graphs in polynomial time, Discrete Math. 192 (1998), 119-144.
• [8] Jha P. K., Hypercubes, Median graphs and products of graphs: Some algorithmic and combinatorial results, Ph.D. Thesis, Iowa State Univ., 1990.
• [9] Lih K.-W., Wu P.-L., On equitable coloring of bipartite graphs, Discrete Math., 151 (1996), 155-160.
• [10] Meyer W. Equitable coloring, Amer. Math. Monthly 80 (1973), 920-922.
• [11] Sabidussi G., Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957), 515-525.
• [12] Vesztergombi K., Some remarks on the chromatic number of the strong product of graphs, Colloq. Math. Soc. Janos Bolyai 25 (1981), 819-825.
• [13] Yap H. P., Zhang Y., The equitable Delta-coloring conjecture holds for outerplanar graphs, Bulletin of the Inst. of Math. Academia Sinica 25 (1997), 143-149.
• [14] Yap H. P., Zhang Y., Equitable colorings of planar graphs, J. Combin. Math. Combin. Comput. 27 (1998), 97-105.
• [15] Zhu X., A survey on Hedetniemi's conjecture, Taiwanese J. Math. 2 (1998), 1-24.