Geodesic
Generalized Fractional Total Colorings of Graphs
Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 463-473.

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

Let 𝒫 and 𝒬 be additive and hereditary graph properties and let r, s be integers such that r ≥ s. Then an r/s-fractional (𝒫,𝒬)-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 𝒫, all edges of color i induce a subgraph with property 𝒬 and vertices and incident edges have been assigned disjoint sets of colors. The minimum ratio of an r/s-fractional (𝒫,𝒬)-total coloring of G is called fractional (𝒫, 𝒬)-total chromatic number χ_f, 𝒫 ,𝒬^'' (G) = r/s. We show in this paper that χ_f, 𝒫 ,𝒬^'' 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.
Keywords: fractional coloring, total coloring, automorphism group 
@article{DMGT_2015_35_3_a5,
     author = {Karafov\'a, Gabriela and Sot\'ak, Roman},
     title = {Generalized {Fractional} {Total} {Colorings} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {463--473},
     publisher = {mathdoc},
     volume = {35},
     number = {3},
     year = {2015},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a5/}
}
TY  - JOUR
AU  - Karafová, Gabriela
AU  - Soták, Roman
TI  - Generalized Fractional Total Colorings of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2015
SP  - 463
EP  - 473
VL  - 35
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a5/
LA  - en
ID  - DMGT_2015_35_3_a5
ER  - 
%0 Journal Article
%A Karafová, Gabriela
%A Soták, Roman
%T Generalized Fractional Total Colorings of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2015
%P 463-473
%V 35
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a5/
%G en
%F DMGT_2015_35_3_a5
Karafová, Gabriela; Soták, Roman. Generalized Fractional Total Colorings of Graphs. Discussiones Mathematicae. Graph Theory, Tome 35 (2015) no. 3, pp. 463-473. http://geodesic.mathdoc.fr/item/DMGT_2015_35_3_a5/

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

[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

[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

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

[7] J.L. Gross and J. Yellen, Graph Theory and Its Applications, (CRC Press, New York 2006) 58-72.

[8] G. Karafová, Generalized fractional total coloring of complete graphs, Discuss. Math. Graph Theory 33 (2013) 665-676. doi:10.7151/dmgt.1697

[9] A. Kemnitz, M. Marangio, P. Mihók, J. Oravcová and R. Soták, Generalized fractional and circular total colorings of graphs, (2010), preprint.

[10] K. Kilakos and B. Reed, Fractionally colouring total graphs, Combinatorica 13 (1993) 435-440. doi:10.1007/BF01303515

[11] E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory (John Wiley and Sons, New York, 1997).

[12] V.G. Vizing, Some unsolved problems in graph theory, Russian Math. Surveys 23 (1968) 125-141. doi:10.1070/RM1968v023n06ABEH001252