Three-coloring and list three-coloring of graphs without induced paths on seven vertices
From MaRDI portal
Publication:1786047
A graph \(G\) is \(H\)-free if \(G\) does not contain an induced subgraph isomorphic to \(H\). It is known that if \(H\) contains a cycle, then \(k\) -coloring is NP-complete for \(k\geq 3\) for the class of \(H\)-free graphs. In contrast, it is proved in this paper that one can decide whether a given \(P_{7}\)-free graph has a \(3\)-coloring and can find such a coloring, if any, in polynomial time.
Recommendations
- List edge and list total colorings of planar graphs without non-induced 7-cycles
- List 3-coloring graphs with no induced \(P_6 + rP_3\)
- List edge colorings of planar graphs without adjacent 7-cycles
- Total colorings of planar graphs with maximum degree seven and without intersecting 3-cycles
- Obstructions for three-coloring graphs without induced paths on six vertices
- On planar graphs without list 3-coloring
- On uniquely 3-list colorable graphs
- A note on the three color problem on planar graphs without 4- and 5-cycles and without ext-triangular 7-cycles
- Three coloring planar graphs without cycles of length from 4 to 6 or seven cycles with close triangles
- Obstructions for three-coloring and list three-coloring H-free graphs
Cites work
- 3-colorability \(\in \mathcal P\) for \(P_{6}\)-free graphs.
- 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- A New Characterization of P_k-free Graphs
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Closing complexity gaps for coloring problems on \(H\)-free graphs
- Coloring edges and vertices of graphs without short or long cycles
- Coloring the vertices of a graph with majority restrictions on colors
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- Graph colorings with local constraints -- a survey
- scientific article; zbMATH DE number 3896983 (Why is no real title available?)
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- Improved complexity results on \(k\)-coloring \(P _{t }\)-free graphs
- Matrix multiplication via arithmetic progressions
- Narrowing the complexity gap for colouring \((C_{s},P_{t})\)-free graphs
- NP completeness of finding the chromatic index of regular graphs
- On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
- The complexity of colouring problems on dense graphs
- The NP-Completeness of Edge-Coloring
- Three-colourability and forbidden subgraphs. II: Polynomial algorithms
Cited in
(64)- Independent feedback vertex set for P₅-free graphs
- Classifying \(k\)-edge colouring for \(H\)-free graphs
- On list \(k\)-coloring convex bipartite graphs
- On coloring a class of claw-free and hole-twin-free graphs
- An intractability result for the vertex 3-colourability problem
- Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter
- Colouring \((P_r + P_s)\)-free graphs
- Vertex coloring of a graph for memory constrained scenarios
- List 3-coloring \(P_t\)-free graphs with no induced 1-subdivision of \(K_{1 , s}\)
- Better 3-coloring algorithms: excluding a triangle and a seven vertex path
- Structural domination and coloring of some ( P₇ , C₇)-free graphs
- List 3-coloring graphs with no induced \(P_6 + rP_3\)
- Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs
- List k-colouring P_t-free graphs: a mim-width perspective
- Obstructions for three-coloring graphs without induced paths on six vertices
- Coloring of pseudocubic graphs in three colors
- \(H\)-colouring \(P_t\)-free graphs in subexponential time
- Colouring square-free graphs without long induced paths
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- Certifying coloring algorithms for graphs without long induced paths
- New formulations and branch-and-cut procedures for the longest induced path problem
- 3-colouring \(P_t\)-free graphs without short odd cycles
- 4‐Coloring P 6 ‐Free Graphs with No Induced 5‐Cycles
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Colouring square-free graphs without long induced paths
- 3-colorable subclasses of \(P_8\)-free graphs
- On the complexity of the vertex 3-coloring problem for the hereditary graph classes with forbidden subgraphs of small size
- Complexity of C_K-coloring in hereditary classes of graphs
- Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem
- Colouring (P_r+P_s)-Free Graphs
- Colouring H-free graphs of bounded diameter.
- Complexity dichotomy for list-5-coloring with a forbidden induced subgraph
- Finding Large H-Colorable Subgraphs in Hereditary Graph Classes
- Obstructions for three-coloring and list three-coloring H-free graphs
- scientific article; zbMATH DE number 7651174 (Why is no real title available?)
- \(k\)-critical graphs in \(P_5\)-free graphs
- Colouring graphs of bounded diameter in the absence of small cycles
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- k-critical graphs in P₅-free graphs
- On 3-coloring of \((2P_4,C_5)\)-free graphs
- Colouring graphs of bounded diameter in the absence of small cycles
- A refinement on the structure of vertex-critical \((P_5, \mathrm{gem})\)-free graphs
- Complexity of \(C_k\)-coloring in hereditary classes of graphs
- MIP formulations for induced graph optimization problems: a tutorial
- Infinite families of \(k\)-vertex-critical \((P_5, C_5)\)-free graphs
- Four-Coloring \(P_6\)-Free Graphs. I. Extending an Excellent Precoloring
- 3-coloring C₄ or C₃-free diameter two graphs
- A complete classification of the complexity of the vertex 3-colourability problem for quadruples of induced 5-vertex prohibitions
- Four-Coloring \(\boldsymbol{P_6}\)-Free Graphs. II. Finding an Excellent Precoloring
- Vertex-critical ( P₃ + P₁ )-free and vertex-critical (gem, co-gem)-free graphs
- List-3-coloring ordered graphs with a forbidden induced subgraphs
- List 3-coloring on comb-convex and caterpillar-convex bipartite graphs
- A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
- On P₅-free locally split graphs
- Near optimal colourability on (H, K_n - e)-free graphs
- -boundedness and related problems on graphs without long induced paths: a survey
- Complexity of the list homomorphism problem in hereditary graph classes
- Minimal obstructions to C₅-Coloring in hereditary graph classes
- Minimal obstructions to C₅-coloring in hereditary graph classes
- Some classifications of the computational complexity for the vertex 3-colourability problem
- Three-coloring triangle-free graphs without long forbidden paths
- 3-coloring P_t-free graphs with only one prescribed induced odd cycle length
- Sparse induced subgraphs in P₇-Free graphs of bounded clique number
- The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable
This page was built for publication: Three-coloring and list three-coloring of graphs without induced paths on seven vertices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1786047)
