Premium
On the Polarity and Monopolarity of Graphs
Author(s) -
Churchley Ross,
Huang Jing
Publication year - 2014
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.21755
Subject(s) - combinatorics , chordal graph , mathematics , pathwidth , indifference graph , cograph , strong perfect graph theorem , maximal independent set , 1 planar graph , modular decomposition , discrete mathematics , split graph , metric dimension , bipartite graph , time complexity , line graph , graph
Polarity and monopolarity are properties of graphs defined in terms of the existence of certain vertex partitions; graphs with polarity and monopolarity are respectively called polar and monopolar graphs. These two properties commonly generalize bipartite and split graphs, but are hard to recognize in general. In this article we identify two classes of graphs, triangle‐free graphs and claw‐free graphs, restricting to which provide novel impact on the complexity of the recognition problems. More precisely, we prove that recognizing polarity or monopolarity remains NP‐complete for triangle‐free graphs. We also show that for claw‐free graphs the former is NP‐complete and the latter is polynomial time solvable. This is in sharp contrast to a recent result that both polarity and monopolarity can be recognized in linear time for line graphs. Our proofs for the NP‐completeness are simple reductions. The polynomial time algorithm for recognizing the monopolarity of claw‐free graphs uses a subroutine similar to the well‐known breadth‐first search algorithm and is based on a new structural characterization of monopolar claw‐free graphs, a generalization of one for monopolar line graphs obtained earlier.