Colouring exact distance graphs of chordal graphs
Artículo

Access note
Acceso Abierto
Publication date
2020
Author
Abstract
For a graph G = (V, E) and positive integer p, the exact distance-p graph G([hp]) is the graph with vertex set V and with an edge between vertices x and y if and only if x and y have distance p. Recently, there has been an effort to obtain bounds on the chromatic number chi(G([hp])) of exact distance -p graphs for G from certain classes of graphs. In particular, if a graph G has tree -width t, it has been shown that chi(G([hp]) is an element of 0(p(t-1)) for odd p, and chi(G([hp])) E O(pt Delta (G)) for even p. We show that if G is chordal and has tree-width t, then x(G([hp])) E O(p t(2)) for odd p, and chi(G([hp])) is an element of O(p t(2) Delta(G)) for even p.
If we could show that for every graph H of tree -width t there is a chordal graph G of tree-width t which contains H as an isometric subgraph (i.e., a distance preserving subgraph), then our results would extend to all graphs of tree -width t. While we cannot do this, we show that for every graph H of genus g there is a graph G which is a triangulation of genus g and contains H as an isometric subgraph. (C) 2019 Elsevier B.V. All rights reserved.
Patrocinador
Comision Nacional de Investigacion Cientifica y Tecnologica (CONICYT)
PIA/Concurso Apoyo a Centros Cientificos y Tecnologicos de Excelencia con Financiamiento Basal
AFB170001
Indexation
Artículo de publicación ISI Artículo de publicación SCOPUS
Quote Item
Discrete Mathematics 343 (2020) 111769
Collections
The following license files are associated with this item:
Except where otherwise noted, this item's license is described as Attribution-NonCommercial-NoDerivs 3.0 Chile
Related items
Showing items related by title, author, creator and subject.
-
Bonomo, Flavia; Durán Maggiolo, Guillermo; Groshaus, Marina (2007)A new class of graphs related to perfect graphs is defined in this work: coordinated graphs. A graph G is coordinated if the cardinality of a maximum set of cliques of H with a common vertex is equal to the cardinality of ...
-
Alcón, Liliana; Bonomo, Flavia; Durán, Guillermo; Gutierrez, Marisa; Mazzoleni, María; Ries, Bernard; Valencia-Pabon, Mario (Elsevier B.V., 2018)Golumbic, Lipshteyn and Stern [12] proved that every graph can be represented as the edge intersection graph of paths on a grid (EPG graph), i.e., one can associate with each vertex of the graph a nontrivial path on a ...
-
Bonomo-Braberman, Flavia; Durán, Guillermo; Safe, Martín D.; Wagler, Annegret K. (Elsevier, 2020)Perfect graphs form a well-known class of graphs introduced by Berge in the 1960s in terms of a min-max type equality involving two famous graph parameters. In this work, we survey certain variants and subclasses of perfect ...