article

Some results concerning the complexity of restricted colorings of graphs

Author:

Marek KubaleAuthors Info & Claims

Discrete Applied Mathematics, Volume 36, Issue 1

Pages 35 - 46

https://doi.org/10.1016/0166-218X(92)90202-L

Published: 30 March 1992 Publication History

Abstract

No abstract available.

Cited By

View all

Baklan Şen BYaşar Diner ÖErlebach T(2023)List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite GraphsComputing and Combinatorics10.1007/978-3-031-49190-0_12(168-181)Online publication date: 15-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-49190-0_12
Golovach PPaulusma DSong J(2014)Closing complexity gaps for coloring problems on H-free graphsInformation and Computation10.1016/j.ic.2014.02.004237(204-214)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1016/j.ic.2014.02.004
Lucarelli GMilis I(2011)Improved approximation algorithms for the max-edge coloring problemProceedings of the First international ICST conference on Theory and practice of algorithms in (computer) systems10.5555/1987334.1987355(206-216)Online publication date: 18-Apr-2011
https://dl.acm.org/doi/10.5555/1987334.1987355
Show More Cited By

Index Terms

Some results concerning the complexity of restricted colorings of graphs
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

Complexity of generalized colourings of chordal graphs
On colourings of graphs
Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

A k -colouring of a graph G =( V , E ) is a mapping c : V {1,2, , k } such that c ( u ) c ( v ) whenever uv is an edge. The reconfiguration graph of the k -colourings of G contains as its vertex set the k -colourings of G , and two ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Discrete Applied Mathematics

Discrete Applied Mathematics Volume 36, Issue 1

March 30, 1992

90 pages

ISSN:0166-218X

Editor:
Peter L. Hammer
Rutgers Univ., New Brunswick, NJ

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 30 March 1992

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Baklan Şen BYaşar Diner ÖErlebach T(2023)List 3-Coloring on Comb-Convex and Caterpillar-Convex Bipartite GraphsComputing and Combinatorics10.1007/978-3-031-49190-0_12(168-181)Online publication date: 15-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-49190-0_12
Golovach PPaulusma DSong J(2014)Closing complexity gaps for coloring problems on H-free graphsInformation and Computation10.1016/j.ic.2014.02.004237(204-214)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1016/j.ic.2014.02.004
Lucarelli GMilis I(2011)Improved approximation algorithms for the max-edge coloring problemProceedings of the First international ICST conference on Theory and practice of algorithms in (computer) systems10.5555/1987334.1987355(206-216)Online publication date: 18-Apr-2011
https://dl.acm.org/doi/10.5555/1987334.1987355
Lucarelli GMilis I(2011)Improved approximation algorithms for the Max Edge-Coloring problemInformation Processing Letters10.1016/j.ipl.2011.05.019111:16(819-823)Online publication date: 1-Aug-2011
https://dl.acm.org/doi/10.1016/j.ipl.2011.05.019
Bourgeois NLucarelli GMilis IPaschos V(2010)Approximating the max-edge-coloring problemTheoretical Computer Science10.1016/j.tcs.2010.04.031411:34-36(3055-3067)Online publication date: 1-Jul-2010
https://dl.acm.org/doi/10.1016/j.tcs.2010.04.031
Lucarelli GMilis IPaschos V(2009)On the Maximum Edge Coloring ProblemApproximation and Online Algorithms10.1007/978-3-540-93980-1_22(279-292)Online publication date: 13-Jan-2009
https://dl.acm.org/doi/10.1007/978-3-540-93980-1_22
Kobler DRotics U(2003)Edge dominating set and colorings on graphs with fixed clique-widthDiscrete Applied Mathematics10.1016/S0166-218X(02)00198-1126:2-3(197-221)Online publication date: 15-Mar-2003
https://dl.acm.org/doi/10.1016/S0166-218X%2802%2900198-1
Kobler DRotics UKosaraju S(2001)Polynomial algorithms for partitioning problems on graphs with fixed clique-width (extended abstract)Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms10.5555/365411.365510(468-476)Online publication date: 9-Jan-2001
https://dl.acm.org/doi/10.5555/365411.365510
Feder THell P(1998)List Homomorphisms to Reflexive GraphsJournal of Combinatorial Theory Series B10.1006/jctb.1997.181272:2(236-250)Online publication date: 1-Mar-1998
https://dl.acm.org/doi/10.1006/jctb.1997.1812

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Complexity of generalized colourings of chordal graphs

On colourings of graphs

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations