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

DOI10.1016/J.DISC.2009.04.004MaRDI QIDQ1044994zbMATH OpenOpenAlexFDO

Authors 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

distinguishing chromatic numbersdistinguishing numbersinterval graphsPQ-trees

Mathematics Subject Classification ID

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

Recommendations

• On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
• The list distinguishing number equals the distinguishing number for interval graphs
• On computing the distinguishing numbers of trees and forests
• List-distinguishing colorings of graphs
• Distinguishing trees in linear time

Cites work

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

Cited in

(18)

• On the chromatic number of multiple interval graphs and overlap graphs
• Extending precolorings to distinguish group actions
• Proper distinguishing colorings with few colors for graphs with girth at least 5
• On the distinguishing number of cyclic tournaments: towards the Albertson-Collins conjecture
• A note on computable distinguishing colorings
• Distinguishing numbers and distinguishing indices of oriented graphs
• On the local distinguishing chromatic number
• List-distinguishing Cartesian products of cliques
• Distinguishing number of hierarchical products of graphs
• On Computing the Distinguishing Numbers of Planar Graphs and Beyond: A Counting Approach
• Nordhaus-Gaddum theorem for the distinguishing chromatic number
• Distinguishing trees in linear time
• The list distinguishing number equals the distinguishing number for interval graphs
• Inverse Booking Problem: Inverse Chromatic Number Problem in Interval Graphs
• On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two
• Tyshkevich's graph decomposition and the distinguishing numbers of unigraphs
• Distinguishing chromatic numbers of complements of Cartesian products of complete graphs
• On computing the distinguishing numbers of trees and forests

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

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