\((p,k)\)-coloring problems in line graphs. (English) Zbl 1086.05029
Summary: The \((p,k)\)-coloring problems generalize the usual coloring problem by replacing stable sets by cliques and stable sets. Complexities of some variations of \((p,k)\)-coloring problems (split-coloring and cocoloring) are studied in line graphs; polynomial algorithms or proofs of NP-completeness are given according to the complexity status. We show that the most general \((p,k)\)-coloring problems are more difficult than the cocoloring and the split-coloring problems while there is no such relation between the last two problems. We also give complexity results for the problem of finding a maximum \((p,k)\)-colorable subgraph in line graphs. Finally, upper bounds on the optimal values are derived in general graphs by sequential algorithms based on Welsh–Powell and Matula orderings.
References:
| [1] | N. Apollonio, Some constrained covering problems in graphs, Ph.D. Thesis, University of Roma “La Sapienza”, 2002.; N. Apollonio, Some constrained covering problems in graphs, Ph.D. Thesis, University of Roma “La Sapienza”, 2002. |
| [2] | Berge, C., Graphs and Hypergraphs (1973), North-Holland Publishing Company: North-Holland Publishing Company Amsterdam · Zbl 0483.05029 |
| [3] | Cornuéjols, G.; Pulleyblank, W., A matching problem with side conditions, Discrete Math., 29, 135-159 (1980) · Zbl 0446.05031 |
| [4] | Demange, M.; Ekim, T.; de Werra, D., Partitioning cographs into cliques and stable sets, Discrete Optim., 2, 145-153 (2005) · Zbl 1136.05315 |
| [5] | Edmonds, J.; Johnson, E. L., Matchinga well-solved class of integer linear programs, (Proc. Calgary Internat. Conf. on Combinatorial Structures and their Applications. Proc. Calgary Internat. Conf. on Combinatorial Structures and their Applications, Gordon and Breach (1970)), 89-92 · Zbl 0258.90032 |
| [6] | T. Ekim, D. de Werra, On split-coloring problems, J. Combin. Optim., to appear.; T. Ekim, D. de Werra, On split-coloring problems, J. Combin. Optim., to appear. · Zbl 1122.05077 |
| [7] | Feder, T.; Hell, P.; Klein, S.; Motwani, R., List partitions, SIAM J. Discrete Math., 16, 3, 449-478 (2003) · Zbl 1029.05143 |
| [8] | U. Feige, E. Ofek, U. Wieder, Approximating maximum edge coloring in multigraphs, APPROX 2002, Springer, Rome, Italy, 2462 (2002) 108-121.; U. Feige, E. Ofek, U. Wieder, Approximating maximum edge coloring in multigraphs, APPROX 2002, Springer, Rome, Italy, 2462 (2002) 108-121. · Zbl 1013.90110 |
| [9] | Fomin, F. V.; Kratsch, D.; Novelli, J. C., Approximating minimum cocolorings, Inform. Process. Lett., 84, 285-290 (2002) · Zbl 1042.68091 |
| [10] | Gabow, H. N., An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems, (STOC (1983)), 448-456 |
| [11] | Garey, M. R.; Johnson, D. S., Computers and Intractability—a Guide to the Theory of NP-completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 |
| [12] | Gimbel, J.; Kratsch, D.; Stewart, L., On cocolorings and cochromatic numbers of graphs, Discrete Appl. Math., 48, 111-127 (1994) · Zbl 0795.05052 |
| [13] | D. Hartvigsen, Extensions of matching theory, Ph.D. Thesis, Carnegie-Mellon University, 1984.; D. Hartvigsen, Extensions of matching theory, Ph.D. Thesis, Carnegie-Mellon University, 1984. |
| [14] | Hell, P.; Klein, S.; Nogueira, L. T.; Protti, F., Partitioning chordal graphs into independent sets and cliques, Discrete Appl. Math., 141, 185-194 (2004) · Zbl 1043.05097 |
| [15] | Holyer, I., The NP-completeness of edge-coloring, SIAM J. Comput., 10, 4, 718-720 (1981) · Zbl 0473.68034 |
| [16] | Kézdy, A. E.; Snevily, H. S.; Wang, C., Partitioning permutations into increasing and decreasing subsequences, J. Combin. Theory Ser. A, 73, 2, 353-359 (1996) · Zbl 0844.05003 |
| [17] | Lesniak, L.; Straight, H. J., The cochromatic number of a graph, Ars Combin., 3, 39-46 (1977) · Zbl 0394.05020 |
| [18] | Matula, D. W., \(k\)-components clusters and slicings in graphs, SIAM J. Appl. Math., 22, 3, 459-480 (1972) · Zbl 0243.05111 |
| [19] | Matula, D. W.; Beck, L. L., Smallest-last ordering and clusterings and graph coloring algorithms, J. Assoc. Comput. Mach., 30, 3, 417-427 (1983) · Zbl 0628.68054 |
| [20] | Papadimitriou, C., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading · Zbl 0833.68049 |
| [21] | Poljak, S., A note on the stable sets and coloring of graphs, Comment. Math. Univ. Carolinae, 15, 307-309 (1974) · Zbl 0284.05105 |
| [22] | Trotter, L. E., Line-perfect graphs, Math. Programming, 12, 255-259 (1977) · Zbl 0366.05043 |
| [23] | Welsh, D. J.A.; Powell, M. B., An upper bound on the chromatic number of a graph and its application to timetabling problems, Comput. J., 10, 85-87 (1967) · Zbl 0147.15206 |
| [24] | M. Yannakakis, Node- and edge-deletion NP-complete problems, Proc. 10th Annu. ACM Symp. on Theory of Comput., New York, 1978, pp. 253-264.; M. Yannakakis, Node- and edge-deletion NP-complete problems, Proc. 10th Annu. ACM Symp. on Theory of Comput., New York, 1978, pp. 253-264. · Zbl 1282.68131 |
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.
