The computational complexity of weighted vertex coloring for \P₅,K₂,3,K^+_2,3\-free graphs
The complexity of vertex colouring for hereditary families of graphs defined by one forbidden induced subgraph was completely determined by \textit{D. Král'} et al. [Lect. Notes Comput. Sci. 2204, 254--262 (2001; Zbl 1042.68639)]. The complexity is also known for most hereditary families defined by two forbidden induced subgraphs with at most five vertices. It remains open for a few cases including when the forbidden induced subgraphs are \(\{P_5,K_{2,3}\}\) or \(\{P_5,K^+_{2,3}\}\). (Here, \(P_5\) is the path with five vertices, \(K_{2,k}\) is the complete bipartite graph with partite sets of sizes two and \(k\) and \(K^+_{2,k}\) is obtained from \(K_{2,k}\) by adding an edge joining the vertices of degree \(k\).) In the present paper, the authors show that the vertex colouring problem can be solved in polynomial time for the class of graphs with no induced subgraph in \(\{P_5,K_{2,3},K^+_{2,3}\}\). The bulk of the proof deals with the case where such a graph has an induced \(4\)-cycle. It is shown that if there is an induced \(4\)-cycle, then there must be a dominating \(4\)-cycle \(C\). The remaining vertices may be partitioned according to their adjacencies with \(C\). A careful analysis of the structure of the graphs induced by the vertices of a block of this partition and the edges between two such blocks shows that the original graph either has at most twelve vertices, may be obtained in a simple way from a graph with no stable set of size three or has no induced subgraph belonging to \(\{P_5,K_{2,2}\}\). In each of these cases, there is a polynomial time algorithm to determine the chromatic number. The authors' results are actually a mild generalization of those described above, as the authors prove their results in the setting of graphs in which each vertex has a positive integer weight. Now, a vertex colouring is an assignment of a set of colours to each vertex with each set having size equal to the corresponding demand and so that the sets assigned to adjacent vertices have no colour in common. Moving to the weighted version does not affect the complexity.
- Two complexity results for the vertex coloring problem
- Polynomial cases for the vertex coloring problem
- Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- The complexity of the vertex 3-colorability problem for some hereditary classes defined by 5-vertex forbidden induced subgraphs
- A coloring problem on the \(n\)-cube
- A survey on the computational complexity of coloring graphs with forbidden subgraphs
- Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
- Coloring graphs characterized by a forbidden subgraph
- Colouring diamond-free graphs
- Colouring of graphs with Ramsey-type forbidden subgraphs
- Colouring square-free graphs without long induced paths
- Colouring vertices of triangle-free graphs without forests
- Complexity of coloring graphs without paths and cycles
- scientific article; zbMATH DE number 2044943 (Why is no real title available?)
- Minimum total coloring of planar graph
- On coloring a class of claw-free graphs.
- On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
- Optimal channel assignment with list-edge coloring
- Polynomial cases for the vertex coloring problem
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Polynomial-time approximation algorithms for the coloring problem in some cases
- Structure and algorithms for (cap, even hole)-free graphs
- The class of \((P_7, C_4, C_5)\)-free graphs: decomposition, algorithms, and \(\chi \)-boundedness
- The coloring problem for classes with two small obstructions
- The intersection of two vertex coloring problems
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- Two cases of polynomial-time solvability for the coloring problem
- Two complexity results for the vertex coloring problem
- Vertex coloring of graphs with few obstructions
- Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
- The weighted coloring problem for two graph classes characterized by small forbidden induced structures
- Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
- Two complexity results for the vertex coloring problem
- Efficient solvability of the weighted vertex coloring problem for some hereditary class of graphs with 5-vertex prohibitions
- Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes
- A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs
- Polynomial cases for the vertex coloring problem
- Near optimal colourability on (H, K_n - e)-free graphs
This page was built for publication: The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1996748)
