Local Chromatic Number, KY Fan's Theorem, And Circular Colorings View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2006-10

AUTHORS

Gábor Simonyi*, Gábor Tardos†

ABSTRACT

The local chromatic number of a graph was introduced in [14]. It is in between the chromatic and fractional chromatic numbers. This motivates the study of the local chromatic number of graphs for which these quantities are far apart. Such graphs include Kneser graphs, their vertex color-critical subgraphs, the Schrijver (or stable Kneser) graphs; Mycielski graphs, and their generalizations; and Borsuk graphs. We give more or less tight bounds for the local chromatic number of many of these graphs.We use an old topological result of Ky Fan [17] which generalizes the Borsuk–Ulam theorem. It implies the existence of a multicolored copy of the complete bipartite graph K⌈t/2⌉,⌊t/2⌋ in every proper coloring of many graphs whose chromatic number t is determined via a topological argument. (This was in particular noted for Kneser graphs by Ky Fan [18].) This yields a lower bound of ⌈t/2⌉ + 1 for the local chromatic number of these graphs. We show this bound to be tight or almost tight in many cases.As another consequence of the above we prove that the graphs considered here have equal circular and ordinary chromatic numbers if the latter is even. This partially proves a conjecture of Johnson, Holroyd, and Stahl and was independently attained by F. Meunier [42]. We also show that odd chromatic Schrijver graphs behave differently, their circular chromatic number can be arbitrarily close to the other extreme. More... »

PAGES

587-626

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00493-006-0034-x

DOI

http://dx.doi.org/10.1007/s00493-006-0034-x

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1048219738


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Mathematical Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Pure Mathematics", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Alfr\u00e9d R\u00e9nyi Institute of Mathematics, Hungarian Academy of Sciences, POB 127, 1364, Budapest, Hungary", 
          "id": "http://www.grid.ac/institutes/grid.423969.3", 
          "name": [
            "Alfr\u00e9d R\u00e9nyi Institute of Mathematics, Hungarian Academy of Sciences, POB 127, 1364, Budapest, Hungary"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Simonyi*", 
        "givenName": "G\u00e1bor", 
        "id": "sg:person.0677117337.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0677117337.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Alfr\u00e9d R\u00e9nyi Institute of Mathematics, Hungarian Academy of Sciences, POB 127, 1364, Budapest, Hungary", 
          "id": "http://www.grid.ac/institutes/grid.423969.3", 
          "name": [
            "School of Computing Science, Simon Fraser University, Burnaby BC, V5A 1S6, Canada", 
            "Alfr\u00e9d R\u00e9nyi Institute of Mathematics, Hungarian Academy of Sciences, POB 127, 1364, Budapest, Hungary"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tardos\u2020", 
        "givenName": "G\u00e1bor", 
        "id": "sg:person.01020344606.50", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01020344606.50"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006-10", 
    "datePublishedReg": "2006-10-01", 
    "description": "The local chromatic number of a graph was introduced in [14]. It is in between the chromatic and fractional chromatic numbers. This motivates the study of the local chromatic number of graphs for which these quantities are far apart. Such graphs include Kneser graphs, their vertex color-critical subgraphs, the Schrijver (or stable Kneser) graphs; Mycielski graphs, and their generalizations; and Borsuk graphs. We give more or less tight bounds for the local chromatic number of many of these graphs.We use an old topological result of Ky Fan [17] which generalizes the Borsuk\u2013Ulam theorem. It implies the existence of a multicolored copy of the complete bipartite graph K\u2308t/2\u2309,\u230at/2\u230b in every proper coloring of many graphs whose chromatic number t is determined via a topological argument. (This was in particular noted for Kneser graphs by Ky Fan [18].) This yields a lower bound of \u2308t/2\u2309 + 1 for the local chromatic number of these graphs. We show this bound to be tight or almost tight in many cases.As another consequence of the above we prove that the graphs considered here have equal circular and ordinary chromatic numbers if the latter is even. This partially proves a conjecture of Johnson, Holroyd, and Stahl and was independently attained by F. Meunier [42]. We also show that odd chromatic Schrijver graphs behave differently, their circular chromatic number can be arbitrarily close to the other extreme.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00493-006-0034-x", 
    "isAccessibleForFree": true, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "5", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "26"
      }
    ], 
    "keywords": [
      "local chromatic number", 
      "chromatic number", 
      "ordinary chromatic number", 
      "Ky Fan theorem", 
      "fractional chromatic number", 
      "circular chromatic number", 
      "Borsuk\u2013Ulam theorem", 
      "complete bipartite graph", 
      "Ky Fan", 
      "Kneser graphs", 
      "Mycielski graphs", 
      "topological arguments", 
      "Schrijver graphs", 
      "such graphs", 
      "proper coloring", 
      "circular coloring", 
      "fan theorem", 
      "tight bounds", 
      "topological results", 
      "bipartite graphs", 
      "theorem", 
      "number t", 
      "graph", 
      "coloring", 
      "bounds", 
      "conjecture", 
      "generalization", 
      "subgraphs", 
      "number", 
      "existence", 
      "Holroyd", 
      "quantity", 
      "latter", 
      "behave", 
      "circular", 
      "argument", 
      "cases", 
      "Johnson", 
      "results", 
      "Stahl", 
      "Meunier", 
      "extremes", 
      "consequences", 
      "fans", 
      "copies", 
      "study"
    ], 
    "name": "Local Chromatic Number, KY Fan's Theorem, And Circular Colorings", 
    "pagination": "587-626", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1048219738"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00493-006-0034-x"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00493-006-0034-x", 
      "https://app.dimensions.ai/details/publication/pub.1048219738"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-12-01T06:26", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/article/article_428.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00493-006-0034-x"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00493-006-0034-x'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00493-006-0034-x'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-006-0034-x'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-006-0034-x'


 

This table displays all metadata directly associated to this object as RDF triples.

111 TRIPLES      20 PREDICATES      71 URIs      63 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00493-006-0034-x schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N780121fe29944901bf4d143f9ada0ae7
4 schema:datePublished 2006-10
5 schema:datePublishedReg 2006-10-01
6 schema:description The local chromatic number of a graph was introduced in [14]. It is in between the chromatic and fractional chromatic numbers. This motivates the study of the local chromatic number of graphs for which these quantities are far apart. Such graphs include Kneser graphs, their vertex color-critical subgraphs, the Schrijver (or stable Kneser) graphs; Mycielski graphs, and their generalizations; and Borsuk graphs. We give more or less tight bounds for the local chromatic number of many of these graphs.We use an old topological result of Ky Fan [17] which generalizes the Borsuk–Ulam theorem. It implies the existence of a multicolored copy of the complete bipartite graph K⌈t/2⌉,⌊t/2⌋ in every proper coloring of many graphs whose chromatic number t is determined via a topological argument. (This was in particular noted for Kneser graphs by Ky Fan [18].) This yields a lower bound of ⌈t/2⌉ + 1 for the local chromatic number of these graphs. We show this bound to be tight or almost tight in many cases.As another consequence of the above we prove that the graphs considered here have equal circular and ordinary chromatic numbers if the latter is even. This partially proves a conjecture of Johnson, Holroyd, and Stahl and was independently attained by F. Meunier [42]. We also show that odd chromatic Schrijver graphs behave differently, their circular chromatic number can be arbitrarily close to the other extreme.
7 schema:genre article
8 schema:isAccessibleForFree true
9 schema:isPartOf Nc089e1f44d1a4ead86355cbb8f55037d
10 Nde7a29f7554c4f89bfc8c1ccb1b4f937
11 sg:journal.1136493
12 schema:keywords Borsuk–Ulam theorem
13 Holroyd
14 Johnson
15 Kneser graphs
16 Ky Fan
17 Ky Fan theorem
18 Meunier
19 Mycielski graphs
20 Schrijver graphs
21 Stahl
22 argument
23 behave
24 bipartite graphs
25 bounds
26 cases
27 chromatic number
28 circular
29 circular chromatic number
30 circular coloring
31 coloring
32 complete bipartite graph
33 conjecture
34 consequences
35 copies
36 existence
37 extremes
38 fan theorem
39 fans
40 fractional chromatic number
41 generalization
42 graph
43 latter
44 local chromatic number
45 number
46 number t
47 ordinary chromatic number
48 proper coloring
49 quantity
50 results
51 study
52 subgraphs
53 such graphs
54 theorem
55 tight bounds
56 topological arguments
57 topological results
58 schema:name Local Chromatic Number, KY Fan's Theorem, And Circular Colorings
59 schema:pagination 587-626
60 schema:productId N49fc7547db57423f9fd8ef28f15e7456
61 N766c3661cfb4408b8f9d1262d28518f2
62 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048219738
63 https://doi.org/10.1007/s00493-006-0034-x
64 schema:sdDatePublished 2022-12-01T06:26
65 schema:sdLicense https://scigraph.springernature.com/explorer/license/
66 schema:sdPublisher N2cd49edf0c0c4b03aea80d0217c79a49
67 schema:url https://doi.org/10.1007/s00493-006-0034-x
68 sgo:license sg:explorer/license/
69 sgo:sdDataset articles
70 rdf:type schema:ScholarlyArticle
71 N2cd49edf0c0c4b03aea80d0217c79a49 schema:name Springer Nature - SN SciGraph project
72 rdf:type schema:Organization
73 N49fc7547db57423f9fd8ef28f15e7456 schema:name doi
74 schema:value 10.1007/s00493-006-0034-x
75 rdf:type schema:PropertyValue
76 N6d063160f34b457b87035fa71c39c43a rdf:first sg:person.01020344606.50
77 rdf:rest rdf:nil
78 N766c3661cfb4408b8f9d1262d28518f2 schema:name dimensions_id
79 schema:value pub.1048219738
80 rdf:type schema:PropertyValue
81 N780121fe29944901bf4d143f9ada0ae7 rdf:first sg:person.0677117337.10
82 rdf:rest N6d063160f34b457b87035fa71c39c43a
83 Nc089e1f44d1a4ead86355cbb8f55037d schema:issueNumber 5
84 rdf:type schema:PublicationIssue
85 Nde7a29f7554c4f89bfc8c1ccb1b4f937 schema:volumeNumber 26
86 rdf:type schema:PublicationVolume
87 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
88 schema:name Mathematical Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
91 schema:name Pure Mathematics
92 rdf:type schema:DefinedTerm
93 sg:journal.1136493 schema:issn 0209-9683
94 1439-6912
95 schema:name Combinatorica
96 schema:publisher Springer Nature
97 rdf:type schema:Periodical
98 sg:person.01020344606.50 schema:affiliation grid-institutes:grid.423969.3
99 schema:familyName Tardos†
100 schema:givenName Gábor
101 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01020344606.50
102 rdf:type schema:Person
103 sg:person.0677117337.10 schema:affiliation grid-institutes:grid.423969.3
104 schema:familyName Simonyi*
105 schema:givenName Gábor
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0677117337.10
107 rdf:type schema:Person
108 grid-institutes:grid.423969.3 schema:alternateName Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, POB 127, 1364, Budapest, Hungary
109 schema:name Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, POB 127, 1364, Budapest, Hungary
110 School of Computing Science, Simon Fraser University, Burnaby BC, V5A 1S6, Canada
111 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...