On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results

DOI10.1016/j.disc.2009.04.004zbMath1213.05071OpenAlexW2122327283MaRDI QIDQ1044994

Christine T. Cheng

Publication date: 15 December 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2009.04.004

zbMATH Keywords

interval graphsPQ-treesdistinguishing numbersdistinguishing chromatic numbers

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Extending precolorings to distinguish group actions ⋮ Proper distinguishing colorings with few colors for graphs with girth at least 5 ⋮ Distinguishing number of hierarchical products of graphs ⋮ Nordhaus-Gaddum theorem for the distinguishing chromatic number ⋮ List-distinguishing Cartesian products of cliques ⋮ On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two ⋮ Distinguishing numbers and distinguishing indices of oriented graphs ⋮ The list distinguishing number equals the distinguishing number for interval graphs ⋮ On the distinguishing number of cyclic tournaments: towards the Albertson-Collins conjecture ⋮ Distinguishing chromatic numbers of complements of Cartesian products of complete graphs ⋮ On the local distinguishing chromatic number

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On computing the distinguishing numbers of trees and forests
• The distinguishing chromatic number
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A note on the asymptotic and computational complexity of graph distinguishability
• The distinguishing number of the hypercube
• Symmetry breaking in graphs
• Incidence matrices and interval graphs
• The distinguishing number of the augmented cube and hypercube powers
• On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
• Linear Time Automorphism Algorithms for Trees, Interval Graphs, and Planar Graphs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs

This page was built for publication: On computing the distinguishing and distinguishing chromatic numbers of interval graphs and other results