The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs (Q1996748): Difference between revisions

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.