ArticleOriginal scientific text
Title
Generalized total colorings of graphs
Authors 1, 2, 2, 3, 4
Affiliations
- Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra, prof. Z. Szafrana 4a, 65-516 Zielona Góra, Poland
- Computational Mathematics, Technische Universität Braunschweig, Pockelsstr. 14, 38106 Braunschweig, Germany
- Department of Applied Mathematics and Informatics, Faculty of Economics, Technical University of Košice, B. Nĕmcovej 32, 04001 Košice
- Mathematical Institute of Slovak Academy of Sciences, Gresákova 6, 04001 Košice, Slovakia
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
Bibliography
- 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.
- 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.
- 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.
- R.L. Brooks, On coloring the nodes of a network, Math. Proc. Cambridge Phil. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X.
- 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.
- R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems equivalent to BPI, Scientia Math. Japonicae 56 (2002) 171-180.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- V.G. Vizing, On an estimate of the chromatic class of a p-graph (in Russian), Metody Diskret. Analiz. 3 (1964) 25-30.
Pages:
209-222
Main language of publication
English
Received
2009-12-07
Accepted
2010-09-28
Published
2011
DOI: 10.7151/dmgt.1540
Exact and natural sciences