The maximal clique and colourability of curve contact graphs

DOI10.1016/S0166-218X(97)00075-9zbMath0898.05025OpenAlexW2261837551MaRDI QIDQ1382253

Petr Hliněný

Publication date: 25 March 1998

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

independence numberchromatic numberpolynomial algorithmcontact graphproblemsmaximal cliqueline segment contact representation

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

Coloring Jordan Regions and Curves ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ On contact graphs of paths on a grid ⋮ Coloring non-crossing strings ⋮ Classes and recognition of curve contact graphs

Cites Work

• Unnamed Item
• Unnamed Item
• String graphs. II: Recognizing string graphs is NP-hard
• String graphs requiring exponential representations
• Intersection graphs of curves in the plane
• Classes and recognition of curve contact graphs
• Intersection graphs of segments
• Representation of a finite graph by a set of intervals on the real line
• On Triangle Contact Graphs

This page was built for publication: The maximal clique and colourability of curve contact graphs