Colouring square-free graphs without long induced paths
From MaRDI portal
Publication:2323345
DOI10.1016/j.jcss.2019.06.002zbMath1429.68081arXiv1805.08270OpenAlexW2962758275MaRDI QIDQ2323345
Serge Gaspers, Shenwei Huang, Daniël Paulusma
Publication date: 30 August 2019
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.08270
Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items
The vertex colourability problem for \(\{\text{claw}, \text{butterfly}\}\)-free graphs is polynomial-time solvable, Clique‐width: Harnessing the power of atoms, The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Complexity of coloring graphs without paths and cycles
- Vertex coloring of graphs with few obstructions
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Determining the chromatic number of triangle-free \(2P_3\)-free graphs in polynomial time
- The coloring problem for classes with two small obstructions
- Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
- Two complexity results for the vertex coloring problem
- Some new hereditary classes where graph coloring remains NP-hard
- Polynomial cases for the vertex coloring problem
- On rigid circuit graphs
- Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
- MSOL partitioning problems on graphs of bounded treewidth and clique-width
- Recent developments on graphs of bounded clique-width
- Decomposition by clique separators
- Coloring the hypergraph of maximal cliques of a graph with no long path
- Triangle-free graphs with no six-vertex induced path
- Linearly \(\chi\)-bounding \((P_6,C_4)\)-free graphs
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- Three-coloring and list three-coloring of graphs without induced paths on seven vertices
- Edge dominating set and colorings on graphs with fixed clique-width
- Algorithmic graph theory and perfect graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Upper bounds to the clique width of graphs
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Colouring diamond-free graphs
- Clique cutsets beyond chordal graphs
- Solving the clique cover problem on (bull, \(C_4\))-free graphs
- Coloring graphs without short cycles and long induced paths
- On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem
- Approximating clique-width and branch-width
- On a property of the class of n-colorable graphs
- List coloring in the absence of two subgraphs
- Linear Time Algorithm for Computing a Small Biclique in Graphs without Long Induced Paths
- A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
- Colouring square-free graphs without long induced paths.
- The NP-Completeness of Edge-Coloring
- Uniquely Colourable Graphs and the Hardness of Colouring Graphs of Large Girth
- Graph Classes: A Survey
- On rank-width of even-hole-free graphs
- 3-Colorable Subclasses of $P_8$-Free Graphs
- NP completeness of finding the chromatic index of regular graphs
- Hereditary graph classes: When the complexities of <scp>coloring</scp> and <scp>clique cover</scp> coincide
- Square-Free Graphs with No Six-Vertex Induced Path
- ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
- Narrowing the Complexity Gap for Colouring (C s ,P t )-Free Graphs
- Improved Bounds for the Flat Wall Theorem
- Graph colouring and the probabilistic method
- Two cases of polynomial-time solvability for the coloring problem
