Discussiones Mathematicae Graph Theory 33(1) (2013)
167-179

doi: 10.7151/dmgt.1649

*Dedicated to Mieczysław Borowiecki on the occasion of his 70 ^{th} birthday*

Arnfried Kemnitz
Computational Mathematics, Technical University Braunschweig | Peter Mihók Mathematical Institute | Margit Voigt
Faculty of Information Technology and Mathematics, University of Applied Sciences |

A (*P*,*Q*)-total independent set
T = V_{T} ∪E_{T} ⊆ V ∪E is the union of a set V_{T} of vertices and a
set E_{T} of edges of G such that for the graphs induced by the sets V_{T}
and E_{T} it holds that G[V_{T}] ∈ *P*, G[E_{T}] ∈ *Q*, and
G[V_{T}] and G[E_{T}] are disjoint. Let *T*_{P,Q} be the set of all
(*P*,*Q*)-total independent sets of G.

Let L(x) be a set of admissible colors for every element x ∈ V ∪E. The graph G is called
(*P*,*Q*)-total (a,b)-list colorable if for each list
assignment L with |L(x) | = a for all x ∈ V ∪E it is possible to
choose a subset C(x) ⊆ L(x) with |C(x) | = b for all x ∈ V ∪E such that the set T_{i} which is defined by T_{i} = {x ∈ V ∪E: i ∈ C(x)} belongs to *T*_{P,Q} for every color i. The ( *P*,*Q*)-choice ratio
chr_{P,Q}(G) of G is defined as the infimum of all
ratios a/b such that G is (*P*,*Q*)-total (a,b)-list
colorable.

We give a direct proof of χ ′ ′_{f,P,Q}(G) = chr_{P,Q}(G) for all simple graphs G and we present for
some properties *P* and *Q* new bounds for the (*P*, *Q*)-total chromatic number and for
the (*P*,*Q*)-choice ratio of a graph G.

**Keywords:** graph property, total coloring, *( P,Q)*-total coloring, fractional coloring, fractional

**2010 Mathematics Subject Classification:** 05C15, 05C75.

[1] | N. Alon and K.A. Berman, Regular hypergraphs, Gordon's Lemma, Steinitz' Lemma and invariant theory, J. Combin. Theory (A) 43 (1986) 91--97, doi: 10.1016/0097-3165(86)90026-9. |

[2] | N. Alon, Zs. Tuza, and M. Voigt, Choosability and fractional chromatic number, Discrete Math. 165/166 (1997) 31--38, doi: 10.1016/S0012-365X(96)00159-8. |

[3] | I. Bárány, A vector-sum theorem and its application to improving flow shop guarantees, Math. Oper. Res. 6 (1981) 445--452, doi: 10.1287/moor.6.3.445. |

[4] | M. Behzad, Graphs and their chromatic numbers (PhD Thesis, Michigan State University, 1965). |

[5] | O.,V. Borodin, On the total colouring of planar graphs, J. Reine Angew. Math. 394 (1989) 180--185. |

[6] | M. Borowiecki, I. Broere, M. Frick, P. Mihók, and G. Semanišin, Survey of hereditary properties of graphs, Discuss. Math. Graph Theory 17 (1997) 5--50, doi: 10.7151/dmgt.1037. |

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

[8] | M. Borowiecki and P. Mihók, Hereditary properties of graphs, in: V.R. Kulli, (Ed.), Advances in Graph Theory, Vishwa International Publications, Gulbarga, (1991) 42--69. |

[9] | A.J.W. Hilton and H.R. Hind, Total chromatic number of graphs having large maximum degree, Discrete Math. 117 (1993) 127--140, doi: 10.1016/0012-365X(93)90329-R. |

[10] | T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience, New York, NY, 1995). |

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

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

[13] | A.V. Kostochka, The total chromatic number of any multigraph with maximum degree five is at most seven, Discrete Math. 162 (1996) 199--214, doi: 10.1016/0012-365X(95)00286-6. |

[14] | P. Mihók, Zs. Tuza, and M. Voigt, Fractional , Tatra Mt. Math. Publ. -colourings and P-choice-ratioP18 (1999) 69--77. |

[15] | M. Molloy and B. Reed, A bound on the total chromatic number, Combinatorica 18 (1998) 241--280, doi: 10.1007/PL00009820. |

[16] | M. Molloy and B. Reed, Graph colouring and the probabilistic method, Algorithms Combin. 23 (Springer, New York, NY, 2002). |

[17] | D.P. Sanders and Y. Zhao, On total , J. Graph Theory 9-coloring planar graphs of maximum degree seven31 (1999) 67--73, doi: 10.1002/(SICI)1097-0118(199905)31:1<67::AID-JGT6>3.0.CO;2-C. |

[18] | E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory (John Wiley & Sons, New York, 1997) http://www.ams.jhu.edu/∼ers/fgt. |

[19] | S.V. Sevastyanov, On approximate solutions of scheduling problems, Metody Diskr. Analiza 32 (1978) 66--75 (in Russian). |

[20] | Zs. Tuza, M. Voigt, On a conjecture of Erdös, Rubin and Taylor, Tatra Mt. Math. Publ. 9 (1996) 69--82. |

[21] | V.G. Vizing, On an estimate of the chromatic class of a , Diskret. Analiz. p-graph3 (1964) 25--30 (in Russian). |

[22] | H.P. Yap, Total Colourings of Graphs (Lecture Notes in Mathematics 1623, Springer, Berlin, 1996). |

Received 19 March 2012

Revised 23 August 2012

Accepted 23 August 2012