Discussiones Mathematicae Graph Theory 31(2) (2011) 209-222
doi: 10.7151/dmgt.1540

[BIBTex] [PDF] [PS]

GENERALIZED TOTAL COLORINGS OF GRAPHS

Mieczysław Borowiecki

Faculty of Mathematics, Computer Science and Econometrics
University of Zielona Góra
prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
e-mail: m.borowiecki@wmie.uz.zgora.pl

Arnfried Kemnitz, Massimiliano Marangio

Computational Mathematics
Technische Universität Braunschweig
Pockelsstr. 14, 38106 Braunschweig, Germany
e-mail: m.marangio@tu-bs.de
e-mail: a.kemnitz@tu-bs.de

Peter Mihók

Department of Applied Mathematics and Informatics
Faculty of Economics, Technical University of Košice
B. Nemcovej 32, 04001 Košice, and
Mathematical Institute of Slovak Academy of Sciences
Gresákova 6, 04001 Košice, Slovakia
e-mail: peter.mihok@tuke.sk

Abstract

An additive hereditary property of graphs is a class of simple graphs which is closed under unions, subgraphs and isomorphism. Let P and Q be additive hereditary properties of graphs. A (P,Q)-total coloring of a simple graph G is a coloring of the vertices V(G) and edges E(G) of G such that for each color i the vertices colored by i induce a subgraph of property P, the edges colored by i induce a subgraph of property Q and incident vertices and edges obtain different colors. In this paper we present some general basic results on (P,Q)-total colorings. We determine the (P,Q)-total chromatic number of paths and cycles and, for specific properties, of complete graphs. Moreover, we prove a compactness theorem for (P,Q)-total colorings.

Keywords: hereditary properties, generalized total colorings, paths, cycles, complete graphs.

2010 Mathematics Subject Classification: 05C15.

References

[1] M. Borowiecki, I. Broere, M. Frick, P. Mihók and G. Semanišin, A survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5-50, doi: 10.7151/dmgt.1037.
[2] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli (ed.): Advances in Graph Theory, (Vishwa International Publication, Gulbarga, 1991) pp. 42-69.
[3] I. Broere, S. Dorfling and E. Jonck, Generalized chromatic numbers and additive hereditary properties of graphs, Discuss. Math. Graph Theory 22 (2002) 259-270, doi: 10.7151/dmgt.1174.
[4] R.L. Brooks, On coloring the nodes of a network, Math. Proc. Cambridge Phil. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X.
[5] S.A. Burr, An inequality involving the vertex arboricity and edge arboricity of a graph, J. Graph Theory 10 (1986) 403-404, doi: 10.1002/jgt.3190100315.
[6] R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems equivalent to BPI, Scientia Math. Japonicae 56 (2002) 171-180.
[7] G. Chartrand and H.V. Kronk, The point arboricity of planar graphs, J. London Math. Soc. 44 (1969) 612-616, doi: 10.1112/jlms/s1-44.1.612.
[8] N.G. de Bruijn and P. Erdös, A colour problem for infinite graphs and a problem in the theory of relations, Indag. Math. 13 (1951) 371-373.
[9] M.J. Dorfling and S. Dorfling, Generalized edge-chromatic numbers and additive hereditary properties of graphs, Discuss. Math. Graph Theory 22 (2002) 349-359, doi: 10.7151/dmgt.1180.
[10] A. Kemnitz and M. Marangio, [r,s,t]-colorings of graphs, Discrete Math. 307 (2007) 199-207, doi: 10.1016/j.disc.2006.06.030.
[11] A. Kemnitz, M. Marangio and P. Mihók, [r,s,t]-chromatic numbers and hereditary properties of graphs, Discrete Math. 307 (2007) 916-922, doi: 10.1016/j.disc.2005.11.055.
[12] P. Mihók and G. Semanišin, Unique factorization theorem and formal concept analysis, in: S. Ben Yahia et al. (eds.): Concept Lattices and Their Applications. Fourth International Conference, CLA 2006, Tunis, Tunisia, October 30-November 1, 2006. LNAI 4923. (Springer, Berlin, 2008) pp. 231-238.
[13] C.St.J.A. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964) 12, doi: 10.1112/jlms/s1-39.1.12.
[14] V.G. Vizing, On an estimate of the chromatic class of a p-graph (in Russian), Metody Diskret. Analiz. 3 (1964) 25-30.

Received 7 December 2009
Revised 28 September 2010
Accepted 28 September 2010