Two remarks on circular arc graphs
type: Item
instance of: scholarly article
title: Two remarks on circular arc graphs
zbMATH Open document ID: 0868.05043
DOI: 10.1007/BF01202237
author: Pavol Hell
author: Jing Huang
published in: Graphs and Combinatorics
publication date: 1997-08-18T00:00:00Z
review text: A graph \(G\) is said to be a circular arc graph if there exist circular arcs A\(g\), \(g\in V(G)\), such that \(g\), \(g'\) are adjacent in \(G\) if and only if the corresponding A\(g\), A\(_{g'}\) intersect. This paper shows that a graph with clique covering number two is a circular arc graph if and only if its edges can be coloured by two colours so that no induced four-cycle contains two opposite edges of the same colour.
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 989830
zbMATH Keywords: clique covering number
zbMATH Keywords: circular arc graph
MaRDI profile type: Publication
cites work: Finding maximum cliques on circular-arc graphs
cites work: A Linear Algorithm for Maximum Weight Cliques in Proper Circular Arc Graphs
cites work: Q3140413
cites work: List homomorphisms and circular arc graphs
cites work: Transitiv orientierbare Graphen
cites work: Algorithms on circular-arc graphs
cites work: Q3328583
cites work: Lexicographic orientation and representation algorithms for comparability graphs, proper circular arc graphs, and proper interval graphs
cites work: Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
cites work: $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
cites work: An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
cites work: Circular-arc graphs with clique cover number two
cites work: Characterization problems for graphs, partially ordered sets, lattices, and families of sets
cites work: Matrix characterizations of circular-arc graphs
cites work: Coloring a Family of Circular Arcs
cites work: An Efficient Test for Circular-Arc Graphs
full work available at URL: https://doi.org/10.1007/bf01202237
OpenAlex ID: W2042309505
description: scientific article; zbMATH DE number 989830