Precoloring Extension (PrExt) for Interval Graphs
Abstract
Keywords
Full Text:
PDFReferences
Marcotte, P.D. Seymour, (1990), “Extending an Edge Coloring “, Journal of Graph Theory, vol.14, pp. 563-573.
Neil Robertson, P.D. Seymour, (1986),“Graph Minors. II. Algorithmic Aspects of Tree Width”, Journal of Algorithmics”, vol 7, pp. 309-322.
M. Hujter, Zs. Tuza, (1993) “Pre Coloring Extension II. Graphs Classes Related to Bipartite Graphs”, Acta Math. Univ. Comenianae, vol. 62, pp.1-11.
Alan Tucker, (1980), “An Efficient test for circular-arc Graphs” , SIAM Journal of Comput, vol.9,pp. 1-24.
Dan Beinstock, (1990), “On Embedding Graphs in Trees”,Journal of Combin. Theory Ser. B 49, pp. 103-136.
Michael O. Albertson and Jaon P. Hutchinson, (2004), “Extending Precoloring of Sub Graphs of Locally Planar Graphs”,European Journalof Combin.vol. 25, pp. 863-871.
Flavia Bonomo, Guillermo Duran, Javier Marenco, (2006), “Exploring the Complexity Boundary between Colorings and list Coloring”, Electronic Notes in Discrete Math.vol. 25, pp.41-47.
Michael O. Albertson, Douglas B. West, (2006), “Extending Precoloring to Circular Colorings”,J. Combin. Theory Ser. B 96, pp.472-481.
Margit Voigt, (2009), “Precoloring Extension for 2-Connected Graphs with Maximum Degree Three”,Discrete Math.vol. 309, pp. 4926-493.
Carsten Thomassen, (2008), “2-List-Coloring Planar Graphs without Monochromatic Triangles”J. Combin. Theory Ser. B 98, pp. 1337-1348.
Manu Basavaraju and L. Sunil Chandran, (2008), “Acyclic Edge Coloring of Subcubic Graphs”,Discrete Math. Vol.308, pp. 66250-66253.
Lei Zhen Cai, (2003), “Parameterized Complexity of Vertex coloring”,Discrete Applied Math. Vol 127, pp. 415-429.
J. Kratochvil, (1993), “Precoloring Extension with Fixed Color Bound”Acta Math. Univ. Comenianae 62, pp.139-153.
Y. Ganjali, M. Ghebleh, H. Hajiabolhassan, M. Mirzazadeh, B.S. Sadjad, “Uniquely 2-List Colorable Graphs”.
Mathew Cropper, Andras Gyarfas, Jeno Lehel, (2002) “Edge List Multi Coloring Trees: An Extension of Halls Theorem”, Hungarian Academy of Sciences
M.Hujter and Zs. Tuza, “Precoloring Extension III. Classes of Perfect Graphs” Hungarian Academy of Sciences.
M.R. Garey, D.S. Johnson, G.L. Miller and C.H. Papadimitriou, (1980) “The Complexity of Coloring Circular Arcs and Chords”SIAM J. Algebraic Discrete Methods Vol.1, pp. 216-222.
M.R. Garey, D.S. Johnson, H.C. (1976), “An Application of Graphs to Printed Circuit Testing”, IEEE Trans. On Circuits and Systems 23.
Daniel Marx, (2003), “List Edge Multi Coloring in Graphs with Few Cycles”J. Graph Theory (to appear).
Miklos Biro, Mihaly Hujter, Zsolt T uza, (1992) “Precoloring Extension. I. IntervalGraphs”, Discrete Math. 100, pp.267-279.
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution 3.0 License.