Bipartable graphs
type: Item
instance of: scholarly article
title: Bipartable graphs
zbMATH Open document ID: 0599.05050
DOI: 10.1016/0095-8956(88)90050-0
author: B. George
published in: Journal of Combinatorial Theory. Series B
publication date: 1988-01-01T00:00:00Z
review text: We consider a construction which associates with a graph G another graph G' such that if G' is a bipartite graph, G is perfectly orderable. For such a graph G we give a polynomial algorithm for an optimal coloring by delivering a perfect order on his nodes. This class of graphs is shown to be different from the known classes of perfectly orderable graphs.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 3966127
zbMATH Keywords: bipartite graph
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: optimal coloring
zbMATH Keywords: perfectly orderable graphs
MaRDI profile type: Publication
full work available at URL: 0095-8956(88)90050-0
OpenAlex ID: W4213049991
cites work: Q5615282
cites work: Which line-graphs are perfectly orderable?
cites work: On brittle graphs
cites work: Four classes of perfectly orderable graphs
cites work: Tolerance graphs
Recommended article: Bipartization of graphs
Recommended article: Bipartite bithreshold graphs
Recommended article: Graphoidal bipartite graphs
Recommended article: Bipartite subgraphs
Recommended article: Bisplit graphs
Recommended article: Q4208001
Recommended article: Q3509720
Recommended article: Bipartite-perfect graphs
Recommended article: On the bipartition of graphs
description: scientific article; zbMATH DE number 3966127