Rankings of graphs
Identifieur interne : 001135 ( Istex/Checkpoint ); précédent : 001134; suivant : 001136Rankings of graphs
Auteurs : H. L. Bodlaender [Pays-Bas] ; J. S. Deogun [États-Unis] ; K. Jansen [Allemagne] ; T. Kloks [Pays-Bas] ; D. Kratsch [Allemagne] ; H. Müller [Allemagne] ; Zs. Tuza [Hongrie]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1995.
Abstract
Abstract: A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶E → {1, 2, ⋯, t}) of a graph G=(V, E) is a vertex (edge) t-ranking if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The vertex ranking number χ r (G) (edge ranking number $$\chi '_r \left( G \right)$$ ) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. Among others it is shown that χ r (G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize those graphs where the vertex ranking number χ r and the chromatic number χ coincide on all induced subgraphs, show that χ r (G)=χ(G) implies χ(G)=ω(G) (largest clique size) and give a formula for $$\chi '_r \left( {K_n } \right)$$ .
Url:
DOI: 10.1007/3-540-59071-4_56
Affiliations:
- Allemagne, Hongrie, Pays-Bas, États-Unis
- Hongrie centrale, Nebraska, Utrecht (province)
- Budapest, Utrecht
- Université d'Utrecht
Links toward previous steps (curation, corpus...)
Links to Exploration step
ISTEX:C10AA9E81094CD92694FF008D94185143272318FLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Rankings of graphs</title>
<author><name sortKey="Bodlaender, H L" sort="Bodlaender, H L" uniqKey="Bodlaender H" first="H. L." last="Bodlaender">H. L. Bodlaender</name>
</author>
<author><name sortKey="Deogun, J S" sort="Deogun, J S" uniqKey="Deogun J" first="J. S." last="Deogun">J. S. Deogun</name>
</author>
<author><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name>
</author>
<author><name sortKey="Kloks, T" sort="Kloks, T" uniqKey="Kloks T" first="T." last="Kloks">T. Kloks</name>
</author>
<author><name sortKey="Kratsch, D" sort="Kratsch, D" uniqKey="Kratsch D" first="D." last="Kratsch">D. Kratsch</name>
</author>
<author><name sortKey="Muller, H" sort="Muller, H" uniqKey="Muller H" first="H." last="Müller">H. Müller</name>
</author>
<author><name sortKey="Tuza, Zs" sort="Tuza, Zs" uniqKey="Tuza Z" first="Zs." last="Tuza">Zs. Tuza</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:C10AA9E81094CD92694FF008D94185143272318F</idno>
<date when="1995" year="1995">1995</date>
<idno type="doi">10.1007/3-540-59071-4_56</idno>
<idno type="url">https://api.istex.fr/document/C10AA9E81094CD92694FF008D94185143272318F/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001572</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001572</idno>
<idno type="wicri:Area/Istex/Curation">001460</idno>
<idno type="wicri:Area/Istex/Checkpoint">001135</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001135</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Rankings of graphs</title>
<author><name sortKey="Bodlaender, H L" sort="Bodlaender, H L" uniqKey="Bodlaender H" first="H. L." last="Bodlaender">H. L. Bodlaender</name>
<affiliation wicri:level="4"><country xml:lang="fr">Pays-Bas</country>
<wicri:regionArea>Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht</wicri:regionArea>
<orgName type="university">Université d'Utrecht</orgName>
<placeName><settlement type="city">Utrecht</settlement>
<region nuts="2">Utrecht (province)</region>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Pays-Bas</country>
</affiliation>
</author>
<author><name sortKey="Deogun, J S" sort="Deogun, J S" uniqKey="Deogun J" first="J. S." last="Deogun">J. S. Deogun</name>
<affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country>
<wicri:regionArea>Department of Computer Science and Engineering, University of Nebraska-Lincoln, 68588-0115, Lincoln, NE</wicri:regionArea>
<placeName><region type="state">Nebraska</region>
</placeName>
</affiliation>
</author>
<author><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name>
<affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286, Trier</wicri:regionArea>
<wicri:noRegion>54286, Trier</wicri:noRegion>
<wicri:noRegion>Trier</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Kloks, T" sort="Kloks, T" uniqKey="Kloks T" first="T." last="Kloks">T. Kloks</name>
<affiliation wicri:level="1"><country xml:lang="fr">Pays-Bas</country>
<wicri:regionArea>Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O.Box 513, 5600, MB Eindhoven</wicri:regionArea>
<wicri:noRegion>MB Eindhoven</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Kratsch, D" sort="Kratsch, D" uniqKey="Kratsch D" first="D." last="Kratsch">D. Kratsch</name>
<affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena</wicri:regionArea>
<wicri:noRegion>07740, Jena</wicri:noRegion>
<wicri:noRegion>Jena</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Muller, H" sort="Muller, H" uniqKey="Muller H" first="H." last="Müller">H. Müller</name>
<affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena</wicri:regionArea>
<wicri:noRegion>07740, Jena</wicri:noRegion>
<wicri:noRegion>Jena</wicri:noRegion>
</affiliation>
</author>
<author><name sortKey="Tuza, Zs" sort="Tuza, Zs" uniqKey="Tuza Z" first="Zs." last="Tuza">Zs. Tuza</name>
<affiliation wicri:level="3"><country xml:lang="fr">Hongrie</country>
<wicri:regionArea>Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111, Budapest</wicri:regionArea>
<placeName><settlement type="city">Budapest</settlement>
<region nuts="2">Hongrie centrale</region>
</placeName>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>1995</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="eISSN">1611-3349</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">C10AA9E81094CD92694FF008D94185143272318F</idno>
<idno type="DOI">10.1007/3-540-59071-4_56</idno>
<idno type="ChapterID">24</idno>
<idno type="ChapterID">Chap24</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass></textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶E → {1, 2, ⋯, t}) of a graph G=(V, E) is a vertex (edge) t-ranking if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The vertex ranking number χ r (G) (edge ranking number $$\chi '_r \left( G \right)$$ ) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. Among others it is shown that χ r (G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize those graphs where the vertex ranking number χ r and the chromatic number χ coincide on all induced subgraphs, show that χ r (G)=χ(G) implies χ(G)=ω(G) (largest clique size) and give a formula for $$\chi '_r \left( {K_n } \right)$$ .</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
<li>Hongrie</li>
<li>Pays-Bas</li>
<li>États-Unis</li>
</country>
<region><li>Hongrie centrale</li>
<li>Nebraska</li>
<li>Utrecht (province)</li>
</region>
<settlement><li>Budapest</li>
<li>Utrecht</li>
</settlement>
<orgName><li>Université d'Utrecht</li>
</orgName>
</list>
<tree><country name="Pays-Bas"><region name="Utrecht (province)"><name sortKey="Bodlaender, H L" sort="Bodlaender, H L" uniqKey="Bodlaender H" first="H. L." last="Bodlaender">H. L. Bodlaender</name>
</region>
<name sortKey="Bodlaender, H L" sort="Bodlaender, H L" uniqKey="Bodlaender H" first="H. L." last="Bodlaender">H. L. Bodlaender</name>
<name sortKey="Kloks, T" sort="Kloks, T" uniqKey="Kloks T" first="T." last="Kloks">T. Kloks</name>
</country>
<country name="États-Unis"><region name="Nebraska"><name sortKey="Deogun, J S" sort="Deogun, J S" uniqKey="Deogun J" first="J. S." last="Deogun">J. S. Deogun</name>
</region>
</country>
<country name="Allemagne"><noRegion><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name>
</noRegion>
<name sortKey="Kratsch, D" sort="Kratsch, D" uniqKey="Kratsch D" first="D." last="Kratsch">D. Kratsch</name>
<name sortKey="Muller, H" sort="Muller, H" uniqKey="Muller H" first="H." last="Müller">H. Müller</name>
</country>
<country name="Hongrie"><region name="Hongrie centrale"><name sortKey="Tuza, Zs" sort="Tuza, Zs" uniqKey="Tuza Z" first="Zs." last="Tuza">Zs. Tuza</name>
</region>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Checkpoint
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 001135 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Checkpoint/biblio.hfd -nk 001135 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Wicri/Rhénanie |area= UnivTrevesV1 |flux= Istex |étape= Checkpoint |type= RBID |clé= ISTEX:C10AA9E81094CD92694FF008D94185143272318F |texte= Rankings of graphs }}
![]() | This area was generated with Dilib version V0.6.31. | ![]() |