# Generalized total colorings of graphs

Mieczysław Borowiecki; Arnfried Kemnitz; Massimiliano Marangio; Peter Mihók

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 2, page 209-222
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topMieczysław Borowiecki, et al. "Generalized total colorings of graphs." Discussiones Mathematicae Graph Theory 31.2 (2011): 209-222. <http://eudml.org/doc/270805>.

@article{MieczysławBorowiecki2011,

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.},

author = {Mieczysław Borowiecki, Arnfried Kemnitz, Massimiliano Marangio, Peter Mihók},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {hereditary properties; generalized total colorings; paths; cycles; complete graphs},

language = {eng},

number = {2},

pages = {209-222},

title = {Generalized total colorings of graphs},

url = {http://eudml.org/doc/270805},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Mieczysław Borowiecki

AU - Arnfried Kemnitz

AU - Massimiliano Marangio

AU - Peter Mihók

TI - Generalized total colorings of graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 2

SP - 209

EP - 222

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

LA - eng

KW - hereditary properties; generalized total colorings; paths; cycles; complete graphs

UR - http://eudml.org/doc/270805

ER -

## References

top- [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. Zbl0902.05026
- [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. Zbl1030.05038
- [4] R.L. Brooks, On coloring the nodes of a network, Math. Proc. Cambridge Phil. Soc. 37 (1941) 194-197, doi: 10.1017/S030500410002168X. Zbl0027.26403
- [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. Zbl0651.05030
- [6] R. Cowen, S.H. Hechler and P. Mihók, Graph coloring compactness theorems equivalent to BPI, Scientia Math. Japonicae 56 (2002) 171-180. Zbl1023.05048
- [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. Zbl0175.50505
- [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. Zbl0044.38203
- [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. Zbl1030.05039
- [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. Zbl1115.05034
- [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. Zbl1133.05306
- [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. Zbl0119.38805
- [14] V.G. Vizing, On an estimate of the chromatic class of a p-graph (in Russian), Metody Diskret. Analiz. 3 (1964) 25-30.

## Citations in EuDML Documents

top- Gabriela Karafová, Generalized Fractional Total Colorings of Complete Graph
- Mieczysław Borowiecki, Izak Broere, Hamiltonicity and Generalised Total Colourings of Planar Graphs
- Gabriela Karafová, Roman Soták, Generalized Fractional Total Colorings of Graphs
- Arnfried Kemnitz, Peter Mihók, Margit Voigt, Fractional (P,Q)-Total List Colorings of Graphs
- Július Czap, Peter Mihók, Fractional Q-Edge-Coloring of Graphs
- Arnfried Kemnitz, Massimiliano Marangio, Peter Mihók, Janka Oravcová, Roman Soták, Generalized Fractional and Circular Total Colorings of Graphs

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.