Classifying \(k\)-edge colouring for \(H\)-free graphs
From MaRDI portal
Publication:1739218
DOI10.1016/j.ipl.2019.02.006zbMath1481.05045arXiv1810.04379OpenAlexW2963501418MaRDI QIDQ1739218
Paloma T. Lima, Bernard Ries, Esther Galby, Daniël Paulusma
Publication date: 26 April 2019
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.04379
Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (6)
Complete complexity dichotomy for $7$-edge forbidden subgraphs in the edge coloring problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Parameterized complexity of \textsc{maximum edge colorable subgraph} ⋮ A complexity dichotomy for critical values of the b-chromatic number of graphs ⋮ Parameterized complexity of maximum edge colorable subgraph
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A new characterization of \(P_k\)-free graphs
- On the chromatic index of cographs and join graphs
- Edge-colouring and total-colouring chordless graphs
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- The complexity of the edge 3-colorability problem for graphs without two induced fragments each on at most six vertices
- Words and graphs
- NP-completeness of edge-colouring some restricted graphs
- Characterizing and edge-colouring split-indifference graphs
- Complexity classification of the edge coloring problem for a family of graph classes
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- The NP-completeness column: an ongoing guide
- The NP-Completeness of Edge-Coloring
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Graph Classes: A Survey
- NP completeness of finding the chromatic index of regular graphs
- Colouring (P_r+P_s)-Free Graphs
- Four-coloring P6-free graphs
This page was built for publication: Classifying \(k\)-edge colouring for \(H\)-free graphs