Coloring, packing and embedding of graphs
type: Dataset
description: In this thesis, we investigate some problems in graph theory, namelythe graph coloring problem, the graph packing problem and tree pattern matchingfor XML query processing. The common point between these problems is that theyuse labeled graphs.In the first part, we study a new coloring parameter of graphs called the gapvertex-distinguishing edge coloring. It consists in an edge-coloring of a graph G whichinduces a vertex distinguishing labeling of G such that the label of each vertex isgiven by the difference between the highest and the lowest colors of its adjacentedges. The minimum number of colors required for a gap vertex-distinguishing edgecoloring of G is called the gap chromatic number of G and is denoted by gap(G).We will compute this parameter for a large set of graphs G of order n and we evenprove that gap(G) 2 fn E 1; n; n + 1g.In the second part, we focus on graph packing problems, which is an area ofgraph theory that has grown significantly over the past several years. However, themajority of existing works focuses on unlabeled graphs. In this thesis, we introducefor the first time the packing problem for a vertex labeled graph. Roughly speaking,it consists of graph packing which preserves the labels of the vertices. We studythe corresponding optimization parameter on several classes of graphs, as well asfinding general bounds and characterizations.The last part deal with the query processing of a core subset of XML query languages:XML twig queries. An XML twig query, represented as a small query tree,is essentially a complex selection on the structure of an XML document. Matching atwig query means finding all the occurrences of the query tree embedded in the XMLdata tree. Many holistic twig join algorithms have been proposed to match XMLtwig pattern. Most of these algorithms find twig pattern matching in two steps. Inthe first one, a query tree is decomposed into smaller pieces, and solutions againstthese pieces are found. In the second step, all of th…
identifier: NNT: 2012LYO10278
issued: 2026-05-05T10:29:33.514535
language: en
modified: 2026-05-05T10:29:33.514540
contact point: Organization
  fn: CCSD
keyword: appariement-exact-des-documents-xml
keyword: colorations-sommets-distinguantes
keyword: graph-theory
keyword: graphes-etiquetes
keyword: infoeu-reposemanticsdoctoralthesis
keyword: infoinfo-ohcomputer-science-csother-csoh
keyword: labeled-graph
keyword: labeled-packing-of-graphs
keyword: placement-de-graphes-etiquetes
keyword: theorie-des-graphes
keyword: theses
keyword: vertex-distinguishing-edge-coloring
keyword: xml-tree-pattern-matching
landing page: https://theses.hal.science/tel-00995041

Coloring, packing and embedding of graphs
type: Distribution
format: HTML
issued: 2026-05-05T10:29:33.524208
modified: 2026-05-05T10:29:33.498324
access URL: https://theses.hal.science/tel-00995041

test_moissonnage_selune
type: Agent