The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
type: Item
instance of: scholarly article
title: The computational complexity of weighted vertex coloring for \(\{P_5,K_{2,3},K^+_{2,3}\}\)-free graphs
zbMATH Open document ID: 1473.05092
author: O. O. Razvenskaya
author: Panos M. Pardalos
author: D. S. Malyshev
published in: Optimization Letters
publication date: 2021-02-26T00:00:00Z
review text: 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 adj…
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 7315894
zbMATH Keywords: vertex coloring
zbMATH Keywords: hereditary class
zbMATH Keywords: computational complexity
reviewed by: Steven D. Noble
MaRDI profile type: Publication
full work available at URL: s11590-020-01593-0
OpenAlex ID: W3027724754
cites work: The class of (P7,C4,C5)‐free graphs: Decomposition, algorithms, and χ‐boundedness
cites work: Structure and algorithms for (cap, even hole)-free graphs
cites work: Colouring diamond-free graphs
cites work: Colouring of graphs with Ramsey-type forbidden subgraphs
cites work: Colouring vertices of triangle-free graphs without forests
cites work: On colouring \((2P_2,H)\)-free and \((P_5,H)\)-free graphs
cites work: On coloring a class of claw-free graphs.
cites work: The intersection of two vertex coloring problems
cites work: Characterizations of \((4 K_1,C_4,C_5)\)-free graphs
cites work: Colouring square-free graphs without long induced paths
cites work: A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
cites work: Coloring graphs characterized by a forbidden subgraph
cites work: Complexity of coloring graphs without paths and cycles
cites work: Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
cites work: Polynomial cases for the vertex coloring problem
cites work: Q4448764
cites work: A coloring problem on the \(n\)-cube
cites work: Vertex coloring of graphs with few obstructions
cites work: The coloring problem for classes with two small obstructions
cites work: Two cases of polynomial-time solvability for the coloring problem
cites work: Polynomial-time approximation algorithms for the coloring problem in some cases
cites work: The weighted coloring problem for two graph classes characterized by small forbidden induced structures
cites work: Two complexity results for the vertex coloring problem
cites work: Optimal channel assignment with list-edge coloring
cites work: Minimum total coloring of planar graph
DOI: 10.1007/S11590-020-01593-0
description: scientific article; zbMATH DE number 7315894