×

The classification of \(f\)-coloring of graphs with large maximum degree. (English) Zbl 1426.05037

Summary: Let \(G = (V, E)\) be a simple graph with vertex set \(V\) and edge set \(E\). Define an integer-valued function \(f\) on \(V\) such that \(f(v) > 0\) for every \(v\in V\). An \(f\)-coloring of \(G\) is an edge-coloring of it such that each color class appears at every vertex \(v\in V(G)\) at most \(f(v)\) times. In this paper, we give a sufficient condition for a simple graph with large maximum degree to be of \(f\)-class 1.

MSC:

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

References:

[1] Akbari, S.; Chavooshi, M.; Ghanbari, M.; Zare, S., The \(f\)-chromatic index of a graph whose \(f\)-core has maximum degree 2, Can. Math. Bull, 56, 449-458 (2013) · Zbl 1276.05043
[2] Bondy, J.; Murty, U., Graph Theory with Applications (1976), Macmillan Press[M]: Macmillan Press[M] New York · Zbl 1226.05083
[3] L. Hakimi, S.; Kariv, O., A generalization of edge-coloring of graphs, J. Gr. Theory, 10, 139-154 (1986) · Zbl 0601.05021
[4] Holyer, I., The NP-completeness of edge colorings, SIAM J.Comput., 10, 718-720 (1981) · Zbl 0473.68034
[5] Liu, G.; Hou, J.; Cai, J., Some results about \(f\)-critical graphs, Networks, 50, 197-202 (2007) · Zbl 1137.05034
[6] Molloy, M.; Reed, B., Graph Coloring and the Probablistic Method (2002), Springer[M]: Springer[M] Berlin · Zbl 0987.05002
[7] Zhang, X.; Liu, G., Some sufficient conditions for a graph to be \(c_f\)1, Appl. Math. Lett., 19, 38-44 (2006) · Zbl 1079.05034
[8] Zhang, X.; Yan, G.; Cai, J., \(f\)-class two graphs whose \(f\)-cores have maximum degree two, Acta Math. Sin., 30, 601-608 (2014) · Zbl 1288.05106
[9] Zhang, X.; Liu, G., The classification of complete graphs \(k_n\) on \(f\)-coloring, J. Appl. Math. Comput., 19, 127-133 (2005) · Zbl 1080.05035
[10] Zhou, X.; Nishizeki, T., Edge-coloring and \(f\)-coloring for various classes of graphs, Algorithms Comput. Lect. Notes Comput. Sci., 33, 592-609 (2012)
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.