Convex-Round and Concave-Round Graphs

DOI10.1137/S0895480197322154MaRDI QIDQ4490778zbMATH OpenOpenAlexFDO

Authors Jing Huang, A. Yeo, Jørgen Bang-Jensen

Publication date 20 July 2000

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/s0895480197322154

zbMATH Keywords

coloringHamiltonian cyclelinear algorithmsmaximum cliquemaximum matchingproper circular arc graphsrecognitionround enumerationround graphs

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Circular-Perfect Concave-Round Graphs
• Convex-round graphs are circular-perfect
• Conical and spherical graphs
• scientific article; zbMATH DE number 1743966
• Convexity in Graphs and Hypergraphs
• Roundness properties of graphs
• scientific article; zbMATH DE number 1439489
• scientific article; zbMATH DE number 5139432
• Convexity in oriented graphs
• Graphs with convex balls

Cited in

(8)

• Essential obstacles to Helly circular-arc graphs
• Convex-round graphs are circular-perfect
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• scientific article; zbMATH DE number 3918415 (Why is no real title available?)
• Characterization and linear-time detection of minimal obstructions to concave-round graphs and the circular-ones property
• Circular-arc hypergraphs: rigidity via connectedness
• Counting kernels in directed graphs with arbitrary orientations
• Boundedness for proper conflict-free and odd colorings

This page was built for publication: Convex-Round and Concave-Round Graphs

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