Geodesic
Generalized total colorings of graphs
Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 2, pp. 209-222.

Voir la notice de l'article provenant de la source Library of Science

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 
@article{DMGT_2011_31_2_a0,
     author = {Borowiecki, Mieczys{\l}aw and Kemnitz, Arnfried and Marangio, Massimiliano and Mih\'ok, Peter},
     title = {Generalized total colorings of graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {209--222},
     publisher = {mathdoc},
     volume = {31},
     number = {2},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a0/}
}
TY  - JOUR
AU  - Borowiecki, Mieczysław
AU  - Kemnitz, Arnfried
AU  - Marangio, Massimiliano
AU  - Mihók, Peter
TI  - Generalized total colorings of graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2011
SP  - 209
EP  - 222
VL  - 31
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a0/
LA  - en
ID  - DMGT_2011_31_2_a0
ER  - 
%0 Journal Article
%A Borowiecki, Mieczysław
%A Kemnitz, Arnfried
%A Marangio, Massimiliano
%A Mihók, Peter
%T Generalized total colorings of graphs
%J Discussiones Mathematicae. Graph Theory
%D 2011
%P 209-222
%V 31
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a0/
%G en
%F DMGT_2011_31_2_a0
Borowiecki, Mieczysław; Kemnitz, Arnfried; Marangio, Massimiliano; Mihók, Peter. Generalized total colorings of graphs. Discussiones Mathematicae. Graph Theory, Tome 31 (2011) no. 2, pp. 209-222. http://geodesic.mathdoc.fr/item/DMGT_2011_31_2_a0/

[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.