DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

PDF

Discussiones Mathematicae Graph Theory 33(1) (2013) 167-179
DOI: https://doi.org/10.7151/dmgt.1649

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

[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 P-colourings and P-choice-ratio, Tatra Mt. Math. Publ. 18 (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 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.
[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 p-graph, Diskret. Analiz. 3 (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

Close