Bipolarizable graphs
type: Item
instance of: scholarly article
title: Bipolarizable graphs
zbMATH Open document ID: 0699.05050
DOI: 10.1016/0012-365X(90)90176-I
author: N. E. Zubov
published in: Discrete Mathematics
publication date: 1990-01-01T00:00:00Z
review text: Perfectly orderable graphs are those for which an order of the nodes can be found such that for any subgraph \(G'\) of G the sequential node coloring algorithm (``always use the smaller possible colour'') gives an optimal coloring for \(G'\). Bipolarisable graphs admit a perfect order such that for any chain \(P_ 4(a,b,c,d)\) of 4 nodes we have \(a>b\) and \(c<d\). This class of perfectly orderable graphs is compared with other known classes of perfectly orderable graph.
Mathematics Subject Classification ID: 05C99
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 4145949
zbMATH Keywords: Perfectly orderable graphs
zbMATH Keywords: sequential node coloring algorithm
zbMATH Keywords: Bipolarisable graphs
reviewed by: H. N. V. Temperley
MaRDI profile type: Publication
cites work: Q5615282
cites work: Q3347930
cites work: Four classes of perfectly orderable graphs
cites work: Bipartable graphs
cites work: On brittle graphs
cites work: All variations on perfectly orderable graphs
full work available at URL: 0012-365x(90)90176-i
OpenAlex ID: W2912622671
Recommended article: Weak bipolarizable graphs
Recommended article: Q3809836
Recommended article: Graphoidal bipartite graphs
Recommended article: Bipartite bithreshold graphs
Recommended article: Bipartable graphs
Recommended article: Bipartite graphs as polynomials and polynomials as bipartite graphs
Recommended article: Pancyclic and Bipancyclic Graphs
Recommended article: Bipolar fuzzy graphs
Recommended article: Q3795708
Recommended article: Equistarable bipartite graphs
description: scientific article; zbMATH DE number 4145949