×

Generalized fractional total colorings of graphs. (English) Zbl 1317.05059

Summary: Let \(\mathcal P\) and \(\mathcal Q\) be additive and hereditary graph properties and let \(r, s\) be integers such that \(r \geq s\). Then an \(\frac{r}{s}\)-fractional \((\mathcal{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,\dots, r\}\) to each vertex and each edge, moreover, for any color \(i\) all vertices of color \(i\) induce a subgraph with property \(\mathcal P\), all edges of color \(i\) induce a subgraph with property \(\mathcal Q\) and vertices and incident edges have been assigned disjoint sets of colors. The minimum ratio of an \(\frac{r}{s}\)-fractional \((\mathcal{P,Q})\)-total coloring of \(G\) is called fractional \((\mathcal{P,Q})\)-total chromatic number \(\chi''_{f,\mathcal{P,Q}}(G) = \frac{r}{s}\). We show in this paper that \(\chi''_{f,\mathcal{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.

MSC:

05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[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.; · Zbl 0221.05062
[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; · Zbl 0902.05026
[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; · Zbl 1234.05076
[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.; · Zbl 0693.05029
[7] J.L. Gross and J. Yellen, Graph Theory and Its Applications, (CRC Press, New York 2006) 58-72.; · Zbl 1082.05001
[8] G. Karafová, Generalized fractional total coloring of complete graphs, Discuss. Math. Graph Theory 33 (2013) 665-676. doi:10.7151/dmgt.1697; · Zbl 1370.05066
[9] A. Kemnitz, M. Marangio, P. Mihók, J. Oravcová and R. Soták, Generalized fractional and circular total colorings of graphs, (2010), preprint.; · Zbl 1317.05060
[10] K. Kilakos and B. Reed, Fractionally colouring total graphs, Combinatorica 13 (1993) 435-440. doi:10.1007/BF01303515; · Zbl 0795.05056
[11] E.R. Scheinerman and D.H. Ullman, Fractional Graph Theory (John Wiley and Sons, New York, 1997).; · Zbl 0891.05003
[12] V.G. Vizing, Some unsolved problems in graph theory, Russian Math. Surveys 23 (1968) 125-141. doi:10.1070/RM1968v023n06ABEH001252; · Zbl 0192.60502
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.