Powers of cycles, powers of paths, and distance graphs

DOI10.1016/j.dam.2010.03.012zbMath1213.05148MaRDI QIDQ531605

Dieter Rautenbach, Min Chih Lin, Francisco J. Soulignac, Jayme Luiz Szwarcfiter

Publication date: 19 April 2011

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

Full work available at URL: https://www.db-thueringen.de/servlets/MCRFileNodeServlet/dbt_derivate_00017388/IfM_Preprint_M_09_10.pdf

zbMATH Keywords

cycle; path; distance graph; circular arc graph; interval graph; circulant graph

Mathematics Subject Classification ID

05C38: Paths and cycles

05C12: Distance in graphs

Related Items

A characterization of line graphs that are squares of graphs, Biclique-colouring verification complexity and biclique-colouring power graphs, On Hamiltonian paths in distance graphs, Boxicity of circular arc graphs, Graph classes with and without powers of bounded clique-width, Computing square roots of trivially perfect and threshold graphs, Short Models for Unit Interval Graphs, Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory, Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear-time algorithm for proper interval graph recognition
• Simple linear time recognition of unit interval graphs
• Colouring the real line
• Colouring prime distance graphs
• Polynomial time algorithms for recognizing and isomorphism testing of cyclic tour-naments
• Circular chromatic numbers and fractional chromatic numbers of distance graphs
• A short proof that `proper = unit'
• Chromatic number of prime distance graphs
• The chromatic numbers of distance graphs
• Recognizing circulant graphs of prime order in polynomial time
• Linear-time recognition of circular-arc graphs
• Coloring of integer distance graphs
• A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
• The Roberts characterization of proper and unit interval graphs
• Certifying Algorithms for Recognizing Proper Circular-Arc Graphs and Unit Circular-Arc Graphs
• Stability in circular arc graphs
• A solution of the isomorphism problem for circulant graphs
• Circulant graphs: recognizing and isomorphism testing in polynomial time
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Recognizing circulant graphs in polynomial time: An application of association schemes