Precoloring extension. I: Interval graphs

DOI10.1016/0012-365X(92)90646-WzbMath0766.05026WikidataQ127976216 ScholiaQ127976216MaRDI QIDQ1198648

S. Singh

Publication date: 16 January 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

chromatic numberNP-completeinterval graphsprecoloring extensionpolynomially solvable

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items

Algorithmic complexity of list colorings ⋮ Parameterized coloring problems on chordal graphs ⋮ Matroids arising from electrical networks ⋮ The \(d\)-precoloring problem for \(k\)-degenerate graphs ⋮ On residual approximation in solution extension problems ⋮ Scheduling with incompatible jobs ⋮ Complexity of list coloring problems with a fixed total number of colors ⋮ Coloration de graphes : fondements et applications ⋮ Extending precolorings to distinguish group actions ⋮ Elimination of parallel copies using code motion on data dependence graphs ⋮ Isomorphism testing for \(T\)-graphs in FPT ⋮ A branch-and-check approach for a wind turbine maintenance scheduling problem ⋮ Generalized coloring for tree-like graphs ⋮ Preassignment requirements in chromatic scheduling ⋮ A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding ⋮ Makespan minimization of multi-slot just-in-time scheduling on single and parallel machines ⋮ Problems on cycles and colorings ⋮ Distance constraints in graph color extensions ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract) ⋮ Flexible list colorings in graphs with special degeneracy conditions ⋮ Extension of some edge graph problems: standard, parameterized and approximation complexity ⋮ Fair allocation algorithms for indivisible items under structured conflict constraints ⋮ Combinatorial problems on \(H\)-graphs ⋮ The complexity of changing colourings with bounded maximum degree ⋮ Some good characterization results relating to the Kőnig-Egerváry theorem ⋮ On Residual Approximation in Solution Extension Problems ⋮ Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs ⋮ Dominator coloring and CD coloring in almost cluster graphs ⋮ Treewidth versus clique number. II: Tree-independence number ⋮ On the tractability of optimization problems on \(H\)-graphs ⋮ Classes of intersection digraphs with good algorithmic properties ⋮ Invited talks ⋮ The maximum-impact coloring polytope ⋮ Unnamed Item ⋮ Routing equal-size messages on a slotted ring ⋮ A survey of graph coloring - its types, methods and applications ⋮ Colouring, constraint satisfaction, and complexity ⋮ Uncolorable mixed hypergraphs ⋮ Precoloring Extension III: Classes of Perfect Graphs ⋮ On coloring problems with local constraints ⋮ On coloring problems with local constraints ⋮ Using Local Search to Speed Up Filtering Algorithms for Some NP-Hard Constraints ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Approximation algorithms for time constrained scheduling ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Flow polynomials as Feynman amplitudes and their \(\alpha\)-representation ⋮ Flexibility of planar graphs -- sharpening the tools to get lists of size four ⋮ Flexible List Colorings in Graphs with Special Degeneracy Conditions ⋮ Aliased register allocation for straight-line programs is NP-complete ⋮ Polyhedral studies of vertex coloring problems: the standard formulation ⋮ Recognizing Proper Tree-Graphs ⋮ Batch coloring of graphs ⋮ Using local search to speed up filtering algorithms for some NP-hard constraints ⋮ Precoloring extension on unit interval graphs ⋮ Unnamed Item ⋮ Hard coloring problems in low degree planar bipartite graphs ⋮ Precoloring extension of co-Meyniel graphs ⋮ On \(H\)-topological intersection graphs ⋮ Graph isomorphism restricted by lists ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ You can't paint yourself into a corner ⋮ Complexity results for minimum sum edge coloring ⋮ The combinatorics of timetabling ⋮ Algorithmic Applications of Tree-Cut Width ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Extending graph colorings ⋮ A TECHNIQUE FOR EXACT COMPUTATION OF PRECOLORING EXTENSION ON INTERVAL GRAPHS ⋮ Electrical networks and hyperplane arrangements ⋮ Complexity of choosing subsets from color sets ⋮ On the number of precolouring extensions ⋮ Two graph-colouring games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey
• List-colourings of graphs
• On embedding graphs in trees
• Asymptotically good list-colorings
• Extending an edge-coloring
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• An Efficient Test for Circular-Arc Graphs
• The Complexity of Coloring Circular Arcs and Chords
• An application of graph coloring to printed circuit testing