The Chromatic Number of the Product of 14-Chromatic Graphs Can BE 13 View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2022-03-14

AUTHORS

Claude Tardif

ABSTRACT

We show that for any n ≥ 13, there exist graphs with chromatic number larger than n whose product has chromatic number n. Our construction is an adaptation of the construction of counterexamples to Hedetniemi’s conjecture devised by Shitov, and adapted by Zhu to graphs with relatively small chromatic numbers. The new tools we introduce are graphs with minimal colourings that are “wide” in the sense of Simonyi and Tardos, and generalised Mycielskians to settle the case n = 13. More... »

PAGES

301-308

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00493-021-4781-5

DOI

http://dx.doi.org/10.1007/s00493-021-4781-5

DIMENSIONS

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


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 Computer Science, Royal Military College of Canada, Kingston, Ontario, Canada", 
          "id": "http://www.grid.ac/institutes/grid.217211.6", 
          "name": [
            "Department of Mathematics and Computer Science, Royal Military College of Canada, Kingston, Ontario, Canada"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tardif", 
        "givenName": "Claude", 
        "id": "sg:person.014205725163.09", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014205725163.09"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf02579374", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026017508", 
          "https://doi.org/10.1007/bf02579374"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s00493-006-0034-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1048219738", 
          "https://doi.org/10.1007/s00493-006-0034-x"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2022-03-14", 
    "datePublishedReg": "2022-03-14", 
    "description": "We show that for any n \u2265 13, there exist graphs with chromatic number larger than n whose product has chromatic number n. Our construction is an adaptation of the construction of counterexamples to Hedetniemi\u2019s conjecture devised by Shitov, and adapted by Zhu to graphs with relatively small chromatic numbers. The new tools we introduce are graphs with minimal colourings that are \u201cwide\u201d in the sense of Simonyi and Tardos, and generalised Mycielskians to settle the case n = 13.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/s00493-021-4781-5", 
    "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": "42"
      }
    ], 
    "keywords": [
      "chromatic number", 
      "small chromatic number", 
      "construction of counterexamples", 
      "Hedetniemi's conjecture", 
      "minimal colorings", 
      "number n.", 
      "case n", 
      "conjecture", 
      "graph", 
      "Shitov", 
      "Mycielskian", 
      "Tardos", 
      "counterexamples", 
      "coloring", 
      "Zhu", 
      "number", 
      "new tool", 
      "construction", 
      "n.", 
      "sense", 
      "tool", 
      "simonyi", 
      "products", 
      "adaptation"
    ], 
    "name": "The Chromatic Number of the Product of 14-Chromatic Graphs Can BE 13", 
    "pagination": "301-308", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1146254936"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00493-021-4781-5"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00493-021-4781-5", 
      "https://app.dimensions.ai/details/publication/pub.1146254936"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-09-02T16:07", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_934.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/s00493-021-4781-5"
  }
]
 

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-021-4781-5'

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-021-4781-5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4781-5'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-021-4781-5'


 

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

89 TRIPLES      21 PREDICATES      50 URIs      40 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00493-021-4781-5 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author N9d68bac0b56244c1adf7c6181e4a59bb
4 schema:citation sg:pub.10.1007/bf02579374
5 sg:pub.10.1007/s00493-006-0034-x
6 schema:datePublished 2022-03-14
7 schema:datePublishedReg 2022-03-14
8 schema:description We show that for any n ≥ 13, there exist graphs with chromatic number larger than n whose product has chromatic number n. Our construction is an adaptation of the construction of counterexamples to Hedetniemi’s conjecture devised by Shitov, and adapted by Zhu to graphs with relatively small chromatic numbers. The new tools we introduce are graphs with minimal colourings that are “wide” in the sense of Simonyi and Tardos, and generalised Mycielskians to settle the case n = 13.
9 schema:genre article
10 schema:isAccessibleForFree false
11 schema:isPartOf N09d363d8bbdc428caaf578edbb01ab74
12 Ne968936c1f764a07be09fec8f8c4f4c4
13 sg:journal.1136493
14 schema:keywords Hedetniemi's conjecture
15 Mycielskian
16 Shitov
17 Tardos
18 Zhu
19 adaptation
20 case n
21 chromatic number
22 coloring
23 conjecture
24 construction
25 construction of counterexamples
26 counterexamples
27 graph
28 minimal colorings
29 n.
30 new tool
31 number
32 number n.
33 products
34 sense
35 simonyi
36 small chromatic number
37 tool
38 schema:name The Chromatic Number of the Product of 14-Chromatic Graphs Can BE 13
39 schema:pagination 301-308
40 schema:productId N8a6f1002664c4f86af9a7f824018113b
41 N913d67f92ddd4817878287739fa35955
42 schema:sameAs https://app.dimensions.ai/details/publication/pub.1146254936
43 https://doi.org/10.1007/s00493-021-4781-5
44 schema:sdDatePublished 2022-09-02T16:07
45 schema:sdLicense https://scigraph.springernature.com/explorer/license/
46 schema:sdPublisher N0307241e817d45c6ab5e1f704ee9f138
47 schema:url https://doi.org/10.1007/s00493-021-4781-5
48 sgo:license sg:explorer/license/
49 sgo:sdDataset articles
50 rdf:type schema:ScholarlyArticle
51 N0307241e817d45c6ab5e1f704ee9f138 schema:name Springer Nature - SN SciGraph project
52 rdf:type schema:Organization
53 N09d363d8bbdc428caaf578edbb01ab74 schema:issueNumber 2
54 rdf:type schema:PublicationIssue
55 N8a6f1002664c4f86af9a7f824018113b schema:name doi
56 schema:value 10.1007/s00493-021-4781-5
57 rdf:type schema:PropertyValue
58 N913d67f92ddd4817878287739fa35955 schema:name dimensions_id
59 schema:value pub.1146254936
60 rdf:type schema:PropertyValue
61 N9d68bac0b56244c1adf7c6181e4a59bb rdf:first sg:person.014205725163.09
62 rdf:rest rdf:nil
63 Ne968936c1f764a07be09fec8f8c4f4c4 schema:volumeNumber 42
64 rdf:type schema:PublicationVolume
65 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
66 schema:name Mathematical Sciences
67 rdf:type schema:DefinedTerm
68 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
69 schema:name Pure Mathematics
70 rdf:type schema:DefinedTerm
71 sg:journal.1136493 schema:issn 0209-9683
72 1439-6912
73 schema:name Combinatorica
74 schema:publisher Springer Nature
75 rdf:type schema:Periodical
76 sg:person.014205725163.09 schema:affiliation grid-institutes:grid.217211.6
77 schema:familyName Tardif
78 schema:givenName Claude
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014205725163.09
80 rdf:type schema:Person
81 sg:pub.10.1007/bf02579374 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026017508
82 https://doi.org/10.1007/bf02579374
83 rdf:type schema:CreativeWork
84 sg:pub.10.1007/s00493-006-0034-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1048219738
85 https://doi.org/10.1007/s00493-006-0034-x
86 rdf:type schema:CreativeWork
87 grid-institutes:grid.217211.6 schema:alternateName Department of Mathematics and Computer Science, Royal Military College of Canada, Kingston, Ontario, Canada
88 schema:name Department of Mathematics and Computer Science, Royal Military College of Canada, Kingston, Ontario, Canada
89 rdf:type schema:Organization
 




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


...