Gap vertex-distinguishing edge colorings of graphs
| Autor: | Eric Duchêne, Hamamache Kheddouci, Mohammed Amin Tahraoui |
|---|---|
| Přispěvatelé: | Graphes, Algorithmes et Multi-Agents (GrAMA), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Graphes, AlgOrithmes et AppLications (GOAL) |
| Jazyk: | angličtina |
| Rok vydání: | 2012 |
| Předmět: |
ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION
Vertex labeling 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics Greedy coloring Computer Science::Discrete Mathematics 0202 electrical engineering electronic engineering information engineering Discrete Mathematics and Combinatorics [INFO]Computer Science [cs] Graph coloring Edge coloring Mathematics List coloring ComputingMethodologies_COMPUTERGRAPHICS Discrete mathematics Neighbourhood (graph theory) 020206 networking & telecommunications Complete coloring Brooks' theorem 010201 computation theory & mathematics Gap vertex-distinguishing edge coloring Fractional coloring MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Discrete Mathematics Discrete Mathematics, Elsevier, 2012, 20, Volume 312, pp.3011-3025 |
| ISSN: | 0012-365X |
| Popis: | In this paper, we study a new coloring parameter of graphs called the gap vertex-distinguishing edge coloring . It consists in an edge-coloring of a graph G which induces a vertex distinguishing labeling of G such that the label of each vertex is given by the difference between the highest and the lowest colors of its adjacent edges. The minimum number of colors required for a gap vertex-distinguishing edge coloring of G is called the gap chromatic number of G and is denoted by gap ( G ) . We here study the gap chromatic number for a large set of graphs G of order n and prove that gap ( G ) ∈ { n − 1 , n , n + 1 } . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect