# Generalized Fractional Total Colorings of Graphs

Gabriela Karafová; Roman Soták

Discussiones Mathematicae Graph Theory (2015)

- Volume: 35, Issue: 3, page 463-473
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topGabriela Karafová, and Roman Soták. "Generalized Fractional Total Colorings of Graphs." Discussiones Mathematicae Graph Theory 35.3 (2015): 463-473. <http://eudml.org/doc/271221>.

@article{GabrielaKarafová2015,

abstract = {Let P and Q be additive and hereditary graph properties and let r, s be integers such that r ≥ s. Then an r/s -fractional (P,Q)-total coloring of a finite graph G = (V,E) is a mapping f, which assigns an s-element subset of the set \{1, 2, . . . , r\} to each vertex and each edge, moreover, for any color i all vertices of color i induce a subgraph with property P, all edges of color i induce a subgraph with property Q and vertices and incident edges have been assigned disjoint sets of colors. The minimum ratio of an r/s -fractional (P,Q)-total coloring of G is called fractional (P,Q)-total chromatic number χ″ƒ,P,Q(G) = r/ s . We show in this paper that χ″ƒ,P,Q of a graph G with o(V (G)) vertex orbits and o(E(G)) edge orbits can be found as a solution of a linear program with integer coefficients which consists only of o(V (G)) + o(E(G)) inequalities.},

author = {Gabriela Karafová, Roman Soták},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {fractional coloring; total coloring; automorphism group.; automorphism group},

language = {eng},

number = {3},

pages = {463-473},

title = {Generalized Fractional Total Colorings of Graphs},

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

volume = {35},

year = {2015},

}

TY - JOUR

AU - Gabriela Karafová

AU - Roman Soták

TI - Generalized Fractional Total Colorings of Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2015

VL - 35

IS - 3

SP - 463

EP - 473

AB - Let P and Q be additive and hereditary graph properties and let r, s be integers such that r ≥ s. Then an r/s -fractional (P,Q)-total coloring of a finite graph G = (V,E) is a mapping f, which assigns an s-element subset of the set {1, 2, . . . , r} to each vertex and each edge, moreover, for any color i all vertices of color i induce a subgraph with property P, all edges of color i induce a subgraph with property Q and vertices and incident edges have been assigned disjoint sets of colors. The minimum ratio of an r/s -fractional (P,Q)-total coloring of G is called fractional (P,Q)-total chromatic number χ″ƒ,P,Q(G) = r/ s . We show in this paper that χ″ƒ,P,Q of a graph G with o(V (G)) vertex orbits and o(E(G)) edge orbits can be found as a solution of a linear program with integer coefficients which consists only of o(V (G)) + o(E(G)) inequalities.

LA - eng

KW - fractional coloring; total coloring; automorphism group.; automorphism group

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

ER -

## References

top- [1] M. Behzad, Graphs and their chromatic numbers, Ph.D. Thesis, (Michigan State University, 1965).
- [2] M. Behzad, The total chromatic number of a graph, a survey, in: Proc. Conf. Oxford, 1969, Combinatorial Mathematics and its Applications, (Academic Press, London, 1971) 1-8. Zbl0221.05062
- [3] 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[Crossref] Zbl0902.05026
- [4] M. Borowiecki, A. Kemnitz, M. Marangio and P. Mihók, Generalized total colorings of graphs, Discuss. Math. Graph Theory 31(2011) 209-222. doi:10.7151/dmgt.1540[WoS][Crossref] Zbl1234.05076
- [5] M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli (Ed.), Advances in Graph Theory (Vishwa International Publication, Gulbarga, 1991) 41-68.
- [6] A.G. Chetwynd, Total colourings, in: Graphs Colourings, R. Nelson and R.J.Wilson (Eds.), Pitman Research Notes in Mathematics 218 (London, 1990) 65-77. Zbl0693.05029
- [7] J.L. Gross and J. Yellen, Graph Theory and Its Applications, (CRC Press, New York 2006) 58-72. Zbl1082.05001
- [8] G. Karafová, Generalized fractional total coloring of complete graphs, Discuss. Math. Graph Theory 33 (2013) 665-676. doi:10.7151/dmgt.1697[Crossref] Zbl06323187
- [9] A. Kemnitz, M. Marangio, P. Mihók, J. Oravcová and R. Soták, Generalized fractional and circular total colorings of graphs, (2010), preprint. Zbl1317.05060
- [10] K. Kilakos and B. Reed, Fractionally colouring total graphs, Combinatorica 13 (1993) 435-440. doi:10.1007/BF01303515[Crossref] Zbl0795.05056
- [11] E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory (John Wiley and Sons, New York, 1997). Zbl0891.05003
- [12] V.G. Vizing, Some unsolved problems in graph theory, Russian Math. Surveys 23 (1968) 125-141. doi:10.1070/RM1968v023n06ABEH001252 [Crossref] Zbl0192.60502