The Complexity of Equitable Vertex Coloring of Graphs

• Autorzy: Furmańczyk H. , Kubale M.
• Konferencja: System Modelling Control (XI; 17-19.10.2005; Zakopane; Poland)
• 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 X=(G). In the paper we give formulas for the equitable chromatic number of some highly-structured graphs and some graph products. We present also two polynomial-time algorithms for equitable graph coloring with suboptimal number of colors.

Słowa kluczowe

EN

artificial intelligence; deduction; induction; predicate logic; resolution; theorem proving

• Wydawca: Wydawnictwo Politechniki Łódzkiej
• Czasopismo: Journal of Applied Computer Science
• Rocznik: 2005
• Tom: Vol. 13, nr 2
• Strony: 95--106
• Opis fizyczny: Bibliogr. 23 poz.

Twórcy

autor

Furmańczyk H.

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

autor

Kubale M.

• Gdańsk University of Technology, Department of Algorithms and System Modeling, Gabriela Narutowicza 11/12, 80-952 Gdańsk, Poland

Bibliografia

• [1] Chen B.-L., Ko M.-T., Lih K.-W.: Equitable and m-bounded coloring of split graphs, LNCS 1120 (1996) 1-5.
• [2] Chen B.-L., Lih K.-W.: Equitable coloring of trees, J. Combin. Theory, Ser. B 61 (1994) 83-87.
• [3] Chen B.-L., Lih K.-W., Wu P.-L.: Equitable coloring and the maximum degree, European J. Combin. 15 (1994) 443-447.
• [4] Chen B.-L., Lih K.-W., Yan J.-H.: Equitable coloring of interval graphs and products of graphs, manuscript (1998).
• [5] Feigenbaum J., Schärfer N. W.: Finding the prime factors of strong direct product graphs in polynomial time, Discrete Math. 109 (1992) 77-102.
• [6] Furmańczyk H.: Equitable and Bounded Coloring of Graphs (in Polish), Ph.D. Thesis, University of Gdańsk, (2005).
• [7] Furmańczyk H.: Equitable coloring of graph products, submitted.
• [8] Furmańczyk H., Giaro K., Kubale M.: Equitable 4-coloring of cacti and edge-cacti in polynomial time, submitted.
• [9] Hajnal A., Szemeredi E.: Proof of a conjecture of Erdös, in: Combinatorial Theory and Its Applications, II 601-623, Colloq. Math. Soc. Janos Bolyai, 4, North-Holland, Amsterdam (1970).
• [10] Holyer I.: The NP-completeness of edge-coloring, SI AM J. Comp. 10 (1981) 718-720.
• [11] Imrich W.: Factoring cardinal product graphs in polynomial time, Discrete Math. 192(1998), 119-144.
• [12] Jha P. K.: Hypercubes, Median graphs and products of graphs: Some algorithmic and combinatorial results, Ph.D. Thesis, Iowa State Univ., (1990).
• [13] Kubale M., Pakulski J., Piwakowski K.: The smallest hard-to-color graph for the SL algorithm, Discrete Math. 164 (1997) 197-212.
• [14] Lam P.Ch.B., Shiu W.Ch., Tong Ch.Sz., Zhang Z.F.: On the equitable chromatic number of complete «-partite graphs, Discrete Appl. Math. 113 (2001) 307-310.
• [15] Lih K.-W., Wu P.-L.: On equitable coloring of bipartite graphs, Discrete Math. 151 (1996) 155-160.
• [16] Matula D.W., Marble G., Isaacson D.: Graph coloring algorithms, in: Graph Theory and Computing, Academic Press, New York (1972) 109-122.
• [17] Meyer W.: Equitable coloring, Amer. Math. Monthly 80 (1973) 920-922.
• [18] Pemmaraju S.V.: Equitable coloring extends Chernoff-Hoeffding bounds, in: Proc. 5th International Workshop on Randomization and Approximation Techniques in Computer Science (APPROXRANDOM 2001) (2001) 285-296.
• [19] Sabidussi G.: Graphs with given group and given graph-theoretical properties, Canad. J. Math. 9 (1957), 515-525.
• [20] Vesztergombi K.: Some remarks on the chromatic number of the strong product of graphs, Colloq. Math. Soc. Janos Bolyai 25 (1981), 819-825.
• [21] Yap H.P., Zhang Y.: On equitable colorings of graphs, manuscript (1996).
• [22] Yap H.P., Zhang Y.: The equitable A-coloring conjecture holds for outerplanar graphs, Bulletin of the Inst, of Math. Academia Sinica 25 (1997) 143-149.
• [23] Yap H.P., Zhang Y.: Equitable colorings of planar graphs, J. Combin. Math. Combin. Comput. 27 (1998).