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

Abstract

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

How to cite

top

Mieczysł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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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
  1. Gabriela Karafová, Generalized Fractional Total Colorings of Complete Graph
  2. Gabriela Karafová, Roman Soták, Generalized Fractional Total Colorings of Graphs
  3. Arnfried Kemnitz, Peter Mihók, Margit Voigt, Fractional (P,Q)-Total List Colorings of Graphs
  4. Július Czap, Peter Mihók, Fractional Q-Edge-Coloring of Graphs
  5. Arnfried Kemnitz, Massimiliano Marangio, Peter Mihók, Janka Oravcová, Roman Soták, Generalized Fractional and Circular Total Colorings of Graphs

NotesEmbed ?

top

You must be logged in to post comments.