Powers of cycles, powers of paths, and distance graphs
From MaRDI portal
Publication:531605
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
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
