Result: [r, s, t]-Chromatic numbers and hereditary properties of graphs
Title:
[r, s, t]-Chromatic numbers and hereditary properties of graphs
Authors:
Source:
Cycles and colourings 2003Discrete mathematics. 307(7-8):916-922
Publisher Information:
Amsterdam: Elsevier, 2007.
Publication Year:
2007
Physical Description:
print, 13 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Mathematics, Mathématiques, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Théorie des graphes, Graph theory, Coloration graphe, Graph colouring, Coloración grafo, Diagramme, Diagram, Diagrama, Nombre chromatique, Chromatic number, Número cromático, Graphe coloré, Propriété héréditaire, Hereditary property, 05C15; [r, s, t]-Chromatic number; Hereditary properties; Generalized colorings
Document Type:
Conference
Conference Paper
File Description:
text
Language:
English
Author Affiliations:
Computational Mathematics, Technische Universität Braunschweig, Pockelsstr. 14, 38106 Braunschweig, Germany
Department of Applied Mathematics and Informatics, Faculty of Economics, Technical University of Kosice, B. Nemcovej 32, 04001 Kosice, Slovakia
Mathematical Institute of Slovak Academy of Sciences, GreŠákova 6, 04001 Kosice, Slovakia
Department of Applied Mathematics and Informatics, Faculty of Economics, Technical University of Kosice, B. Nemcovej 32, 04001 Kosice, Slovakia
Mathematical Institute of Slovak Academy of Sciences, GreŠákova 6, 04001 Kosice, Slovakia
ISSN:
0012-365X
Rights:
Copyright 2007 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Mathematics
Accession Number:
edscal.18531357
Database:
PASCAL Archive
Further Information
Given non-negative integers r, s, and t, an [r, s, t]-coloring of a graph G = (V(G), E(G)) is a mapping c from V(G) U E(G) to the color set {0, 1,..., k- 1},k ∈ N, such that |c(vi) - c(vj)| ≥ r for every two adjacent vertices vi, vj, |c(ei ) - c(ej)| ≥ s for every two adjacent edges ei, ej, and |c(vi) - c(ej)| ≥ t for all pairs of incident vertices and edges, respectively. The [r, s, t]-chromatic number Χr, s, t (G) of G is defined to be the minimum k such that G admits an [r, s, t]-coloring. We characterize the properties O(r, s, t, k) = {G: Χr,s, t, (G) ≤ k} for k = 1,2,3 as well as for k ≥ 3 and max{r, s, t} = 1 using well-known hereditary properties. The main results for k ≥ 3 are summarized in a diagram.