The chromatic number of the product of two 4-chromatic graphs is 4 View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1985-06

AUTHORS

Mohamed El-Zahar, Norbert Sauer

ABSTRACT

For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs. More... »

PAGES

121-126

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf02579374

DOI

http://dx.doi.org/10.1007/bf02579374

DIMENSIONS

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


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": "Department of Mathematics and Statistics, University of Calgary, T2N 1N4, Calgary, Alberta, Canada", 
          "id": "http://www.grid.ac/institutes/grid.22072.35", 
          "name": [
            "Department of Mathematics and Statistics, University of Calgary, T2N 1N4, Calgary, Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "El-Zahar", 
        "givenName": "Mohamed", 
        "id": "sg:person.013715272343.77", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013715272343.77"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics and Statistics, University of Calgary, T2N 1N4, Calgary, Alberta, Canada", 
          "id": "http://www.grid.ac/institutes/grid.22072.35", 
          "name": [
            "Department of Mathematics and Statistics, University of Calgary, T2N 1N4, Calgary, Alberta, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sauer", 
        "givenName": "Norbert", 
        "id": "sg:person.012766733410.11", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012766733410.11"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1985-06", 
    "datePublishedReg": "1985-06-01", 
    "description": "For any graphG and numbern\u22671 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) \u2260g(b). The graph of all such functions is the colouring graph \u2112(G) ofG. We establish first that \u03c7(G)=n+1 implies \u03c7(\u2112(G))=n iff \u03c7(G \u00d7H)=n+1 for all graphsH with \u03c7(H)\u2267n+1. Then we will prove that indeed for all 4-chromatic graphsG \u03c7(\u2112(G))=3 which establishes Hedetniemi\u2019s [3] conjecture for 4-chromatic graphs.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf02579374", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "5"
      }
    ], 
    "keywords": [
      "Hedetniemi's conjecture", 
      "chromatic number", 
      "edges ofG", 
      "graph", 
      "such functions", 
      "conjecture", 
      "graphsG", 
      "ofG", 
      "functionsf", 
      "graphG", 
      "function", 
      "number", 
      "products"
    ], 
    "name": "The chromatic number of the product of two 4-chromatic graphs is 4", 
    "pagination": "121-126", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1026017508"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf02579374"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf02579374", 
      "https://app.dimensions.ai/details/publication/pub.1026017508"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-12-01T06:19", 
    "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_192.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf02579374"
  }
]
 

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/bf02579374'

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/bf02579374'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf02579374'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf02579374'


 

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

77 TRIPLES      20 PREDICATES      38 URIs      30 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf02579374 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N07acac09ea1542528e0468e59d4dca2e
4 schema:datePublished 1985-06
5 schema:datePublishedReg 1985-06-01
6 schema:description For any graphG and numbern≧1 two functionsf, g fromV(G) into {1, 2, ...,n} are adjacent if for all edges (a, b) ofG, f(a) ≠g(b). The graph of all such functions is the colouring graph ℒ(G) ofG. We establish first that χ(G)=n+1 implies χ(ℒ(G))=n iff χ(G ×H)=n+1 for all graphsH with χ(H)≧n+1. Then we will prove that indeed for all 4-chromatic graphsG χ(ℒ(G))=3 which establishes Hedetniemi’s [3] conjecture for 4-chromatic graphs.
7 schema:genre article
8 schema:isAccessibleForFree false
9 schema:isPartOf N97ecebe07bbe49a9a2713d1391f03ef2
10 Na811afb88f78466ab18ad53b3a19cb69
11 sg:journal.1136493
12 schema:keywords Hedetniemi's conjecture
13 chromatic number
14 conjecture
15 edges ofG
16 function
17 functionsf
18 graph
19 graphG
20 graphsG
21 number
22 ofG
23 products
24 such functions
25 schema:name The chromatic number of the product of two 4-chromatic graphs is 4
26 schema:pagination 121-126
27 schema:productId Na0ec40ec34534585b1b903ee95744190
28 Na85de66c91864c1ca60404494f86c643
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026017508
30 https://doi.org/10.1007/bf02579374
31 schema:sdDatePublished 2022-12-01T06:19
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher N00e228f72db1403d9bc2805290eab349
34 schema:url https://doi.org/10.1007/bf02579374
35 sgo:license sg:explorer/license/
36 sgo:sdDataset articles
37 rdf:type schema:ScholarlyArticle
38 N00e228f72db1403d9bc2805290eab349 schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N07acac09ea1542528e0468e59d4dca2e rdf:first sg:person.013715272343.77
41 rdf:rest N14b9c178ff404841bd69c4aee42c907c
42 N14b9c178ff404841bd69c4aee42c907c rdf:first sg:person.012766733410.11
43 rdf:rest rdf:nil
44 N97ecebe07bbe49a9a2713d1391f03ef2 schema:volumeNumber 5
45 rdf:type schema:PublicationVolume
46 Na0ec40ec34534585b1b903ee95744190 schema:name doi
47 schema:value 10.1007/bf02579374
48 rdf:type schema:PropertyValue
49 Na811afb88f78466ab18ad53b3a19cb69 schema:issueNumber 2
50 rdf:type schema:PublicationIssue
51 Na85de66c91864c1ca60404494f86c643 schema:name dimensions_id
52 schema:value pub.1026017508
53 rdf:type schema:PropertyValue
54 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
55 schema:name Mathematical Sciences
56 rdf:type schema:DefinedTerm
57 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
58 schema:name Pure Mathematics
59 rdf:type schema:DefinedTerm
60 sg:journal.1136493 schema:issn 0209-9683
61 1439-6912
62 schema:name Combinatorica
63 schema:publisher Springer Nature
64 rdf:type schema:Periodical
65 sg:person.012766733410.11 schema:affiliation grid-institutes:grid.22072.35
66 schema:familyName Sauer
67 schema:givenName Norbert
68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012766733410.11
69 rdf:type schema:Person
70 sg:person.013715272343.77 schema:affiliation grid-institutes:grid.22072.35
71 schema:familyName El-Zahar
72 schema:givenName Mohamed
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013715272343.77
74 rdf:type schema:Person
75 grid-institutes:grid.22072.35 schema:alternateName Department of Mathematics and Statistics, University of Calgary, T2N 1N4, Calgary, Alberta, Canada
76 schema:name Department of Mathematics and Statistics, University of Calgary, T2N 1N4, Calgary, Alberta, Canada
77 rdf:type schema:Organization
 




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


...