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 (only showing first 100 items - show all)
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
This page was built for publication: Graph colorings with local constraints -- a survey
