Vertex colouring and forbidden subgraphs -- a survey
From MaRDI portal
Publication:1889838
DOI10.1007/s00373-003-0540-1zbMath1056.05065OpenAlexW2089191641MaRDI QIDQ1889838
Ingo Schiermeyer, Bert Randerath
Publication date: 13 December 2004
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: http://e-archive.informatik.uni-koeln.de/453/2/zaik2003-453.pdf
Related Items (77)
Forbidden induced subgraphs for perfectness of claw-free graphs of independence number at least 4 ⋮ 4-Coloring H-Free Graphs When H Is Small ⋮ Square-free graphs with no induced fork ⋮ Chromatic bounds for the subclasses of \(pK_2\)-free graphs ⋮ Vizing bound for the chromatic number on some graph classes ⋮ On the chromatic number of some \(P_5\)-free graphs ⋮ Hierarchical and modularly-minimal vertex colorings ⋮ List coloring in the absence of two subgraphs ⋮ Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time ⋮ 4-colorability of \(P_6\)-free graphs ⋮ Star chromatic bounds ⋮ Simple and three-valued simple minimum coloring games ⋮ Complexity of coloring graphs without paths and cycles ⋮ Coloring graph classes with no induced fork via perfect divisibility ⋮ Partitioning \(H\)-free graphs of bounded diameter ⋮ Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter ⋮ Colouring diamond-free graphs ⋮ The chromatic number of triangle-free and broom-free graphs in terms of the number of vertices ⋮ Colouring \((P_r + P_s)\)-free graphs ⋮ On the chromatic number of (\(P_6\), diamond)-free graphs ⋮ Colouring of graphs with Ramsey-type forbidden subgraphs ⋮ Finding matching cuts in \(H\)-free graphs ⋮ Edge‐colored complete graphs without properly colored even cycles: A full characterization ⋮ Coloring of some crown-free graphs ⋮ Bounds for the chromatic number of some \(pK_2\)-free graphs ⋮ Coloring of a superclass of \(2K_2\)-free graphs ⋮ Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time ⋮ Near optimal colourability on hereditary graph families ⋮ Colouring of \((P_3 \cup P_2)\)-free graphs ⋮ Star coloring of certain graph classes ⋮ A tight linear bound to the chromatic number of \((P_5, K_1 +(K_1 \cup K_3))\)-free graphs ⋮ Total chromatic number of unichord-free graphs ⋮ 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 ⋮ 3-colorability and forbidden subgraphs. I: Characterizing pairs ⋮ Unnamed Item ⋮ 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs. ⋮ Coloring graphs characterized by a forbidden subgraph ⋮ Polynomial \(\chi \)-binding functions and forbidden induced subgraphs: a survey ⋮ Forbidden Subgraphs Generating Almost the Same Sets ⋮ Independent feedback vertex set for \(P_5\)-free graphs ⋮ Improved complexity results on \(k\)-coloring \(P_t\)-free graphs ⋮ On the complexity of 4-coloring graphs without long induced paths ⋮ Two complexity results for the vertex coloring problem ⋮ Upper bounds on the chromatic number of triangle-free graphs with a forbidden subtree ⋮ Contracting to a longest path in H-free graphs ⋮ Coloring vertices of claw-free graphs in three colors ⋮ A Class of Three‐Colorable Triangle‐Free Graphs ⋮ Closing complexity gaps for coloring problems on \(H\)-free graphs ⋮ Mycielski type constructions for hypergraphs associated with fractional colorings ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs ⋮ List coloring in the absence of a linear forest ⋮ First-fit coloring of \(\{P_{5},K_{4}-e\}\)-free graphs ⋮ Chromatic index of graphs with no cycle with a unique chord ⋮ A structure theorem for graphs with no cycle with a unique chord and its consequences ⋮ Chromatic bounds for some classes of \(2 K_2\)-free graphs ⋮ Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs ⋮ Colouring Vertices of Triangle-Free Graphs ⋮ Algorithmic bounds for the chromatic number† ⋮ Efficiency in exponential time for domination-type problems ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Colouring graphs of bounded diameter in the absence of small cycles ⋮ Linear chromatic bounds for a subfamily of \(3K_{1}\)-free graphs ⋮ Coloring Graphs without Short Cycles and Long Induced Paths ⋮ Excluding the fork and antifork ⋮ Colouring (P_r+P_s)-Free Graphs ⋮ Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences ⋮ Colouring H-free graphs of bounded diameter. ⋮ Open Problems on Graph Coloring for Special Graph Classes ⋮ $(2P_2,K_4)$-Free Graphs are 4-Colorable ⋮ Updating the complexity status of coloring graphs without a fixed induced linear forest ⋮ List Coloring in the Absence of a Linear Forest ⋮ Parameterized Pre-Coloring Extension and List Coloring Problems ⋮ Treewidth versus Clique Number. I. Graph Classes with a Forbidden Structure ⋮ Advice complexity of maximum independent set in sparse and bipartite graphs
This page was built for publication: Vertex colouring and forbidden subgraphs -- a survey
