Generalized Fractional Total Colorings of Graphs

Gabriela 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 -