Coloring a Family of Circular Arcs
From MaRDI portal
Publication:4071258
DOI10.1137/0129040zbMath0312.05105OpenAlexW2007610258MaRDI QIDQ4071258
Publication date: 1975
Published in: SIAM Journal on Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0129040
Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)
Related Items
The Complexity of Coloring Circular Arcs and Chords, Periodic assignment and graph colouring, A reduction procedure for coloring perfect \(K_ 4\)-free graphs, On the structure of certain intersection graphs, A note on the Hadwiger number of circular arc graphs, Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection, Unnamed Item, Algorithmic aspects of intersection graphs and representation hypergraphs, Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs, Intersection graphs of Helly families of subtrees, Circular‐Arc Bigraphs and Its Subclasses, An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs, Graphical properties related to minimal imperfection, Algorithms for Necklace Maps, The permutation-path coloring problem on trees., Normal Helly circular-arc graphs and its subclasses, An approach to solving \(A^{k}=J-I\), Catalan structures and dynamic programming in \(H\)-minor-free graphs, A classification of certain graphs with minimal imperfection properties, Interval Routing Schemes for Circular-Arc Graphs, On stable set polyhedra for K//(1,3)free graphs, On coloring problems with local constraints, Boxicity of circular arc graphs, Two remarks on circular arc graphs, On the complexity of bandwidth allocation in radio networks, A Turán-type theorem on chords of a convex polygon, Efficient parallel recognition of some circular arc graphs. I, The complexity of path coloring and call scheduling, 1.5-Approximation algorithm for weighted maximum routing and wavelength assignment on rings, Unnamed Item, Conversion of coloring algorithms into maximum weight independent set algorithms, Circular-arc graph coloring: On chords and circuits in the meeting graph, Cyclic orders, Graphs with Large Obstacle Numbers, Critical perfect graphs and perfect 3-chromatic graphs, Fractional path coloring in bounded degree trees with applications, Coloring geometric range spaces, Wavelength routing of uniform instances in all-optical rings, Hadwiger's conjecture for proper circular arc graphs, Efficient algorithms for wavelength assignment on trees of rings, Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture, On a graph-theoretical model for cyclic register allocation, Lexicographic Orientation Algorithms, Perfect circular arc coloring, Completeness for intersection classes, Finding Hamiltonian circuits in proper interval graphs, On a circle-cover minimization problem, The edge intersection graphs of paths in a tree, On circular critical graphs, Algorithms for preemptive scheduling of different classes of processors to do jobs with fixed times, On the chromatic number of multiple interval graphs and overlap graphs, Covering and coloring problems for relatives of intervals, Dominating sets and domatic number of circular arc graphs, Splittable traffic partition in WDM/SONET rings to minimize SONET ADMs, An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
