Open Access Open Access  Restricted Access Subscription or Fee Access

Precoloring Extension (PrExt) for Interval Graphs

S. Gokilamani, R. Anandhi, M. Revathy

Abstract


Motivated by the ‘Precoloring Extension I. Interval Graphs’ in a series devoted to the study of the following general problem on vertex colorings of graph, “suppose that some vertices of a graph G are assigned to some colors, can this precoloring be extended to a proper coloring of G with at most k colors for some given k?”, this work deals with precoloring for sub graphs of interval graphs. The complexity status of precoloring for interval graphs is investigated. . The work has been extended to precoloring to interval graphs with vertices n = 6. Both extendable and non-extendable interval graphs are investigated and conclusions are arrived.

Keywords


Precoloring Extension (PrExT), Interval Grapghs, Vertex Coloring, Proper Coloring, Extendable Graph & Non Extendable Graph.

Full Text:

PDF

References


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.


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.