Powers of cycles, powers of paths, and distance graphs

DOI10.1016/j.dam.2010.03.012zbMath1213.05148OpenAlexW2003844484MaRDI 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

cyclepathdistance graphcircular arc graphinterval graphcirculant graph

Mathematics Subject Classification ID

Paths and cycles (05C38) Distance in graphs (05C12)

Related Items (11)

A characterization of line graphs that are squares of graphs ⋮ Graph classes with and without powers of bounded clique-width ⋮ Short k‐radius sequences, k‐difference sequences and universal cycles ⋮ Computing square roots of trivially perfect and threshold 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 ⋮ Boxicity of circular arc graphs ⋮ Biclique-colouring verification complexity and biclique-colouring power graphs ⋮ On Hamiltonian paths in distance graphs ⋮ Finding cut-vertices in the square roots of a graph ⋮ Short Models for Unit Interval Graphs

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

This page was built for publication: Powers of cycles, powers of paths, and distance graphs