Graph colorings with local constraints -- a survey
From MaRDI portal
Publication:4210665
DOI10.7151/dmgt.1049zbMath0923.05027OpenAlexW2156678756MaRDI QIDQ4210665
Publication date: 8 November 1998
Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/9c3b9c400197ded6086ede265dd3a167b98ffd6f
Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)
Related Items
Algorithms for vertex-partitioning problems on graphs with fixed clique-width., Ohba's conjecture is true for graphs \(K_{t+2,3,2\ast(k-t-2),1\ast t}\), 4-Coloring H-Free Graphs When H Is Small, Extending precolorings of subgraphs of locally planar graphs, LIST POINT ARBORICITY OF GRAPHS, Path choosability of planar graphs, The \(d\)-precoloring problem for \(k\)-degenerate graphs, Concentration of non‐Lipschitz functions and applications, Unnamed Item, List coloring in the absence of two subgraphs, Precoloring extension involving pairs of vertices of small distance, List Colorings of K5-Minor-Free Graphs With Special List Assignments, Choosability of P 5-Free Graphs, Extending precolorings to distinguish group actions, Using mixed graph coloring to minimize total completion time in job shop scheduling, Complexity of coloring graphs without paths and cycles, Bounds on partial online list colouring, Unnamed Item, List colorings and reducibility, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, Some recent progress and applications in graph minor theory, Time slot scheduling of compatible jobs, Colouring \((P_r + P_s)\)-free graphs, Distance constraints in graph color extensions, On the thinness and proper thinness of a graph, Deciding the On-line Chromatic Number of a Graph with Pre-coloring Is PSPACE-Complete, Data reduction for graph coloring problems, Colouring of graphs with Ramsey-type forbidden subgraphs, Complexity and approximability of extended spanning star forest problems in general and complete graphs, Oriented list colorings of graphs, List colouring of graphs and generalized Dyck paths, Application of polynomial method to on-line list colouring of graphs, On the complexity of some colorful problems parameterized by treewidth, Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time, Local 7-coloring for planar subgraphs of unit disk graphs, Consensus models: computational complexity aspects in modern approaches to the list coloring problem, Coloring graphs without short cycles and long induced paths, A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs, On the parameterized complexity of coloring graphs in the absence of a linear forest, Towards an on-line version of Ohba's conjecture, Beyond Ohba's conjecture: a bound on the choice number of \(k\)-chromatic graphs with \(n\) vertices, Uncolorable mixed hypergraphs, Coloring graphs characterized by a forbidden subgraph, Linear choosability of graphs, Complexity of unique list colorability, Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey, Orientations of graphs with prescribed weighted out-degrees, Chromatic-choosability of hypergraphs with high chromatic number, Improved complexity results on \(k\)-coloring \(P_t\)-free graphs, Two complexity results for the vertex coloring problem, Flexibility of planar graphs -- sharpening the tools to get lists of size four, Upper bounds for the achromatic and coloring numbers of a graph, Polyhedral studies of vertex coloring problems: the standard formulation, WORM colorings of planar graphs, Locally planar graphs are 5-choosable, Hall number for list colorings of graphs: Extremal results, Closing complexity gaps for coloring problems on \(H\)-free graphs, Parameterized complexity of coloring problems: treewidth versus vertex cover, On list coloring Steiner triple systems, Planar graphs without cycles of specific lengths, List coloring in the absence of a linear forest, Extending precolorings to circular colorings, The maximum saving partition problem, List coloring of Cartesian products of graphs, Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs, Three-coloring and list three-coloring of graphs without induced paths on seven vertices, Hard coloring problems in low degree planar bipartite graphs, Restraints permitting the largest number of colourings, Choosability and paintability of the lexicographic product of graphs, Precoloring extension of co-Meyniel graphs, Worm colorings, Randić index and coloring number of a graph, From a zoo to a zoology: Towards a general theory of graph polynomials, Data Reduction for Graph Coloring Problems, Coloring Graphs without Short Cycles and Long Induced Paths, On list \(k\)-coloring convex bipartite graphs, Ohba's conjecture is true for graphs with independence number at most three, Some results on \((a:b)\)-choosability, Open Problems on Graph Coloring for Special Graph Classes, Incidence choosability of graphs, Complexity results for minimum sum edge coloring, List edge multicoloring in graphs with few cycles, Updating the complexity status of coloring graphs without a fixed induced linear forest, Extending graph colorings, List Coloring in the Absence of a Linear Forest, Extremal graphs for the list-coloring version of a theorem of Nordhaus and Gaddum, The Hall number, the Hall index, and the total Hall number of a graph, Color-bounded hypergraphs. I: General results, On list critical graphs, Complexity of choosing subsets from color sets, Extending colorings of planar graphs, A short proof of a conjecture on the \(T_r\)-choice number of even cycles, Inequalities involving the irredundance number of a graph, Domination, coloring and stability in \(P_5\)-reducible graphs, Partial Online List Coloring of Graphs, Characterization of \((2m,m)\)-paintable graphs, Locally planar graphs are 5-paintable, Extremal jumps of the Hall number, Edge dominating set and colorings on graphs with fixed clique-width, Improved bounds for some facially constrained colorings, The Strong Fractional Choice Number and the Strong Fractional Paint Number of Graphs, Coloration de graphes : fondements et applications, NP‐completeness of list coloring and precoloring extension on the edges of planar graphs, Bad list assignments for non‐k $k$‐choosable k $k$‐chromatic graphs with 2k+2 $2k+2$‐vertices, Slow coloring of \(3k\)-connected graphs, The Alon-Tarsi number of a toroidal grid, Optimal secret share distribution in degree splitting communication networks, Unnamed Item, Exploring the complexity boundary between coloring and list-coloring, Exploring the complexity boundary between coloring and list-coloring, Unnamed Item, A broken cycle theorem for the restrained chromatic function, Distance Hereditary Graphs and the Interlace Polynomial, On connected list colorings of graphs, Colouring graphs of bounded diameter in the absence of small cycles, Coloring graphs from lists with bounded size of their union, Colouring graphs of bounded diameter in the absence of small cycles, The last excluded case of Dirac's map‐color theorem for choosability, Colouring (P_r+P_s)-Free Graphs, Colouring H-free graphs of bounded diameter., A Proof of a Conjecture of Ohba, Parameterized Pre-Coloring Extension and List Coloring Problems, Unnamed Item, On (4, 2)‐Choosable Graphs
