# DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

# IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

# Discussiones Mathematicae Graph Theory

Dedicated to Mieczysław Borowiecki on the occasion of his 70th birthday

## Fractional (P,Q)-total List Colorings of Graphs

 Arnfried Kemnitz Computational Mathematics, Technical University Braunschweig Pockelsstr. 14, 38,106 Braunschweig, Germany Peter Mihók Mathematical Institute Margit Voigt Faculty of Information Technology and Mathematics, University of Applied Sciences Friedrich-List-Platz 1, 01,069 Dresden, Germany

## Abstract

Let r,s ∈ ℕ, r ≥ s, and P and Q be two additive and hereditary graph properties. A (P,Q)-total (r,s)-coloring of a graph G = (V,E) is a coloring of the vertices and edges of G by s-element subsets of ℤr such that for each color i, 0 ≤ i ≤ r −1, the vertices colored by subsets containing i induce a subgraph of G with property P, the edges colored by subsets containing i induce a subgraph of G with property Q, and color sets of incident vertices and edges are disjoint. The fractional (P,Q)-total chromatic number χ ′ ′f, P,Q(G) of G is defined as the infimum of all ratios r/s such that G has a (P,Q)-total (r,s)-coloring.

A (P,Q)-total independent set T = VT ∪ET ⊆ V ∪E is the union of a set VT of vertices and a set ET of edges of G such that for the graphs induced by the sets VT and ET it holds that G[VT] ∈ P, G[ET] ∈ Q, and G[VT] and G[ET] are disjoint. Let TP,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 Ti which is defined by Ti = {x ∈ V ∪E:   i ∈ C(x)} belongs to TP,Q for every color i. The ( P,Q)-choice ratio chrP,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) = chrP,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 (P,Q)-total chromatic number, circular coloring, circular (P,Q)-total chromatic number, list coloring, (P,Q)-total (a,b)-list colorings

2010 Mathematics Subject Classification: 05C15, 05C75.

## References

  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.  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.  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.  M. Behzad, Graphs and their chromatic numbers (PhD Thesis, Michigan State University, 1965).  O.,V. Borodin, On the total colouring of planar graphs, J. Reine Angew. Math. 394 (1989) 180--185.  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.  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.  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.  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.  T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley-Interscience, New York, NY, 1995).  A. Kemnitz, M. Marangio, P. Mihók, J. Oravcová, and R. Soták, Generalized fractional and circular total colorings of graphs, preprint.  K. Kilakos and B. Reed, Fractionally colouring total graphs, Combinatorica 13 (1993) 435--440, doi: 10.1007/BF01303515.  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.  P. Mihók, Zs. Tuza, and M. Voigt, Fractional P-colourings and P-choice-ratio, Tatra Mt. Math. Publ. 18 (1999) 69--77.  M. Molloy and B. Reed, A bound on the total chromatic number, Combinatorica 18 (1998) 241--280, doi: 10.1007/PL00009820.  M. Molloy and B. Reed, Graph colouring and the probabilistic method, Algorithms Combin. 23 (Springer, New York, NY, 2002).  D.P. Sanders and Y. Zhao, On total 9-coloring planar graphs of maximum degree seven, J. Graph Theory 31 (1999) 67--73, doi: 10.1002/(SICI)1097-0118(199905)31:1<67::AID-JGT6>3.0.CO;2-C.  E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory (John Wiley & Sons, New York, 1997) http://www.ams.jhu.edu/∼ers/fgt.  S.V. Sevastyanov, On approximate solutions of scheduling problems, Metody Diskr. Analiza 32 (1978) 66--75 (in Russian).  Zs. Tuza, M. Voigt, On a conjecture of Erdös, Rubin and Taylor, Tatra Mt. Math. Publ. 9 (1996) 69--82.  V.G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz. 3 (1964) 25--30 (in Russian).  H.P. Yap, Total Colourings of Graphs (Lecture Notes in Mathematics 1623, Springer, Berlin, 1996).