Matrix characterizations of circular-arc graphs

DOI10.2140/PJM.1971.39.535zbMath0226.05125OpenAlexW2155577291MaRDI QIDQ2548968

Alan C. Tucker

Publication date: 1971

Published in: Pacific Journal of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2140/pjm.1971.39.535

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items (64)

Intersection graphs of paths in a tree ⋮ Extremal Values of the Interval Number of a Graph ⋮ The Complexity of Coloring Circular Arcs and Chords ⋮ The chromatic index of proper circular-arc graphs of odd maximum degree which are chordal ⋮ Tuple domination on graphs with the consecutive-zeros property ⋮ Interval bigraphs and circular arc graphs ⋮ 2-nested matrices: towards understanding the structure of circle graphs ⋮ Solving the canonical representation and star system problems for proper circular-arc graphs in logspace ⋮ Representing digraphs using intervals or circular arcs ⋮ Essential obstacles to Helly circular-arc graphs ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ Circular‐Arc Bigraphs and Its Subclasses ⋮ Short proofs for interval digraphs ⋮ Foreground memory management in data path synthesis ⋮ Proper circular arc graphs as intersection graphs of paths on a grid ⋮ Extending partial representations of circular-arc graphs ⋮ New characterizations of proper interval bigraphs ⋮ On semi-transitive orientability of split graphs ⋮ Proper Helly Circular-Arc Graphs ⋮ On linear and circular structure of (claw, net)-free graphs ⋮ A simpler linear-time recognition of circular-arc graphs ⋮ Algorithms on circular-arc graphs ⋮ Structural results on circular-arc graphs and circle graphs: a survey and the main open problems ⋮ On grid intersection graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ Graph isomorphism and identification matrices: Sequential algorithms ⋮ Intersection representations of matrices by subtrees and unicycles on graphs ⋮ Efficient parallel recognition of some circular arc graphs. II ⋮ Two remarks on circular arc graphs ⋮ Circular-arc hypergraphs: rigidity via connectedness ⋮ On the structure of locally semicomplete digraphs ⋮ Recognizing hidden bicircular networks ⋮ Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs ⋮ Efficient parallel recognition of some circular arc graphs. I ⋮ Approximation and fixed-parameter algorithms for consecutive ones submatrix problems ⋮ A recognition algorithm for the intersection graphs of directed paths in directed trees ⋮ Obstacle numbers of graphs ⋮ Characterization problems for graphs, partially ordered sets, lattices, and families of sets ⋮ Completing colored graphs to meet a target property ⋮ Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms ⋮ Counting kernels in directed graphs with arbitrary orientations ⋮ The circular dimension of a graph ⋮ A constant factor approximation algorithm for boxicity of circular arc graphs ⋮ An extension of a theorem of Fulkerson and Gross ⋮ Hadwiger's conjecture for proper circular arc graphs ⋮ A structure theorem for the consecutive 1's property ⋮ Unnamed Item ⋮ Circularly Compatible Ones, $D$-Circularity, and Proper Circular-Arc Bigraphs ⋮ Circular‐arc digraphs: A characterization ⋮ A selected tour of the theory of identification matrices ⋮ The intersection graphs of subtrees in trees are exactly the chordal graphs ⋮ Structure theorems for some circular-arc graphs ⋮ A good submatrix is hard to find ⋮ Characterizations and recognition of circular-arc graphs and subclasses: a survey ⋮ Dual parameterization of weighted coloring ⋮ Lexicographic Orientation Algorithms ⋮ Circular permutation graphs ⋮ Efficient Local Representations of Graphs ⋮ An O(qn) algorithm to q-color a proper family of circular arcs ⋮ An Optimal Algorithm for Strict Circular Seriation ⋮ Cyclic arrangements with minimum modulo \(m\) winding numbers ⋮ An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs ⋮ Graphs and digraphs represented by intervals and circular arcs ⋮ On the Shannon entropy of the number of vertices with zero in-degree in randomly oriented hypergraphs

This page was built for publication: Matrix characterizations of circular-arc graphs