News Column

Data from Durham University Provide New Insights into Information Technology (Closing complexity gaps for coloring problems on H-free graphs)

August 26, 2014

By a News Reporter-Staff News Editor at Information Technology Newsweekly -- Data detailed on Information Technology have been presented. According to news reporting originating from Durham, United Kingdom, by VerticalNews correspondents, research stated, "If a graph G contains no subgraph isomorphic to some graph H, then G is called H-free. A coloring of a graph G = (V, E) is a mapping c: V ? {1, 2, ...} such that no two adjacent vertices have the same color, i.e., c(u) not equal c(v) if uv is an element of E; if vertical bar c(V)vertical bar

Our news editors obtained a quote from the research from Durham University, "The COLORING problem is to test whether a graph has a coloring with at most k colors for some integer k. The PRECOLORING EXTENSION problem is to decide whether a partial k-coloring of a graph can be extended to a k-coloring of the whole graph for some integer k. The LIST COLORING problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u). By imposing an upper bound l on the size of each L(u) we obtain the l-LIST COLORING problem. We first classify the PRECOLORING EXTENSION problem and the l-LIST COLORING problem for H-free graphs. We then show that 3-LIST COLORING is NP-complete for n-vertex graphs of minimum degree n - 2, i.e., for complete graphs minus a matching, whereas LIST COLORING is fixed-parameter tractable for this graph class when parameterized by the number of vertices of degree n - 2. Finally, for a fixed integer k> 0, the LIST k-COLORING problem is to decide whether a graph allows a coloring, such that every vertex u receives a color from some given set L(u) that must be a subset of {1, ..., k}. We show that LIST 4-COLORING is NP-complete for P-6-free graphs, where P-6 is the path on six vertices."

According to the news editors, the research concluded: "This completes the classification of LIST k-COLORING for P-6-free graphs."

For more information on this research see: Closing complexity gaps for coloring problems on H-free graphs. Information and Computation, 2014;237():204-214. Information and Computation can be contacted at: Academic Press Inc Elsevier Science, 525 B St, Ste 1900, San Diego, CA 92101-4495, USA. (Elsevier -; Information and Computation -

The news editors report that additional information may be obtained by contacting P.A. Golovach, University of Durham, Sch Engn & Comp Sci, Sci Labs, Durham DH1 3LE, United Kingdom. Additional authors for this research include D. Paulusma and J. Song.

Keywords for this news article include: Durham, Europe, United Kingdom, Information Technology

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC

For more stories covering the world of technology, please see HispanicBusiness' Tech Channel

Source: Information Technology Newsweekly

Story Tools Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters