New formulation for coloring circle graphs

DOI10.1007/978-3-032-00281-5_24MaRDI QIDQ6866953zbMATH OpenFDO

Authors Masato Tanaka, Tomomi Matsui

Publication date 28 January 2026

Full work available at URL https://doi.org/10.1007/978-3-032-00281-5_24

zbMATH Keywords

circle graphfractional chromatic numbervertex coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Applications of game theory (91A80)

Cites work

• A decomposition theorem for partially ordered sets
• A generalization of max flow—min cut
• A triangle-free circle graph with chromatic number 5
• Algorithmic graph theory and perfect graphs
• Algorithms and Computation
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Approximating the minimum clique cover and other hard problems in subtree filament graphs
• Circle graphs are quadratically χ‐bounded
• Coloring circle graphs
• Container ship stowage problem complexity and connection to the coloring of circle graphs
• Decomposing a set of points into chains, with applications to permutation and circle graphs
• Dispatching Buses in Parking Depots
• Finding maximum cliques in circle graphs
• scientific article; zbMATH DE number 3121293 (Why is no real title available?)
• scientific article; zbMATH DE number 2145236 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• Improved bounds for colouring circle graphs
• Incidence matrices and interval graphs
• Maximum independent set and maximum clique algorithms for overlap graphs
• New clique and independent set algorithms for circle graphs
• On the asymmetric representatives formulation for the vertex coloring problem
• On the online track assignment problem
• On the Shannon capacity of a graph
• Polynomial algorithms in linear programming
• Reducibility among combinatorial problems
• Scheduling trams in the morning
• Sorting with Complete Networks of Stacks
• Structural results on circular-arc graphs and circle graphs: a survey and the main open problems
• The Complexity of Coloring Circular Arcs and Chords
• The ellipsoid method and its consequences in combinatorial optimization
• The sandwich theorem
• Track assignment
• Trapezoid graphs and generalizations, geometry and algorithms

This page was built for publication: New formulation for coloring circle graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6866953)