Precoloring Extension III: Classes of Perfect Graphs

DOI10.1017/S0963548300001826zbMath0846.05034MaRDI QIDQ4883061

Mihály Hujter, Zsolt Tuza

Publication date: 29 September 1996

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

zbMATH Keywords

algorithmscharacterizationsindependence numberchromatic numberclique numbermaximum clique sizevertex colouringsclasses of perfect graphsprecolouring extendibility

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items (36)

Parameterized coloring problems on chordal graphs ⋮ Coloring problems on bipartite graphs of small diameter ⋮ The \(d\)-precoloring problem for \(k\)-degenerate graphs ⋮ Precoloring extension involving pairs of vertices of small distance ⋮ Extending precolorings to distinguish group actions ⋮ Distance constraints in graph color extensions ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Flexible list colorings in graphs with special degeneracy conditions ⋮ The complexity of changing colourings with bounded maximum degree ⋮ Some good characterization results relating to the Kőnig-Egerváry theorem ⋮ Characterisations and Linear-Time Recognition of Probe Cographs ⋮ Classes of perfect graphs ⋮ A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs ⋮ Colouring, constraint satisfaction, and complexity ⋮ On coloring problems with local constraints ⋮ On coloring problems with local constraints ⋮ Two-dimensional packing with conflicts ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Solving problems on generalized convex graphs via mim-width ⋮ Approximation algorithms for time constrained scheduling ⋮ Exploring the complexity boundary between coloring and list-coloring ⋮ Flexibility of planar graphs -- sharpening the tools to get lists of size four ⋮ Flexible List Colorings in Graphs with Special Degeneracy Conditions ⋮ Systems of distant representatives ⋮ Precoloring extension on unit interval graphs ⋮ A good characterization of cograph contractions ⋮ Precoloring extension of co-Meyniel graphs ⋮ On list \(k\)-coloring convex bipartite graphs ⋮ You can't paint yourself into a corner ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ Complexity results for minimum sum edge coloring ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation ⋮ Extending graph colorings ⋮ b-coloring of m-tight graphs ⋮ Complexity of choosing subsets from color sets ⋮ On the number of precolouring extensions

Cites Work

• Unnamed Item
• Slim graphs
• Complement reducible graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Dominating cliques in \(P_ 5\)-free graphs
• Precoloring extension. I: Interval graphs
• Algorithmic complexity of list colorings
• A characterization of perfect graphs
• Two graph-colouring games
• Extending an edge-coloring
• A Linear Recognition Algorithm for Cographs
• Perfect Elimination and Chordal Bipartite Graphs
• Blocking and anti-blocking pairs of polyhedra
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
• Difference graphs

This page was built for publication: Precoloring Extension III: Classes of Perfect Graphs